Repository: networkx/networkx

Issue:
Ordering of layers in multipartite_layout changed in v2.7. Add a way to control the order?
I am trying to run a script to plot graphs, but they're coming out wrong. I've tracked down the issue to incorrect positions obtained from the multipartite_layout command, which is either ignoring or misordering the node layer information.

### Current Behavior
The positions output by multipartite_layout don't order the layers correctly.

### Expected Behavior
The positions output by multipartite_layout should order the layers by value.

### Steps to Reproduce
Here is a snippet of what I currently get for the position of nodes in a small graph:
import networkx as nx

```
G = nx.DiGraph()
G.add_node('a',layer=2)
G.add_node('b',layer=3)
G.add_node('c',layer=1)
G.add_node('d',layer=2)
G.add_node('e',layer=4)
nx.multipartite_layout(G,align='horizontal',subset_key='layer')

{'d': array([-0.27777778, -0.66666667]),
 'a': array([ 0.27777778, -0.66666667]),
 'b': array([ 0.        , -0.11111111]),
 'c': array([0.        , 0.44444444]),
 'e': array([0., 1.])}
```
What I expect to get out (and can still see if I use an online compiler) is
```
{'d': array([-0.3125, -0.25  ]),
 'a': array([ 0.3125, -0.25  ]),
 'b': array([0.   , 0.375]),
 'c': array([ 0.   , -0.875]),
 'e': array([0., 1.])}
```


### Environment
Python version: 3.9.12
NetworkX version: 2.7.1


### Additional context
On an older computer when I had this issue I was able to resolve it by uninstalling and reinstalling Anaconda. This time I'm working from a new computer with a fresh install and uninstalling/reinstalling doesn't work.


Discussion:

Patch:
diff --git a/.github/workflows/coverage.yml b/.github/workflows/coverage.yml
index d2336e2ee..b015a4996 100644
--- a/.github/workflows/coverage.yml
+++ b/.github/workflows/coverage.yml
@@ -34,5 +34,5 @@ jobs:
 
     - name: Test NetworkX
       run: |
-        pytest --cov=networkx --runslow --doctest-modules --pyargs networkx
+        pytest --cov=networkx --runslow --doctest-modules --durations=20 --pyargs networkx
         codecov
diff --git a/doc/conf.py b/doc/conf.py
index 22fdae6ab..4e7ac42e3 100644
--- a/doc/conf.py
+++ b/doc/conf.py
@@ -135,7 +135,7 @@ html_theme_options = {
         },
     ],
     "external_links": [{"name": "Guides", "url": "https://networkx.org/nx-guides/"}],
-    "navbar_end": ["navbar-icon-links", "version"],
+    "navbar_end": ["theme-switcher", "navbar-icon-links", "version"],
     "page_sidebar_items": ["search-field", "page-toc", "edit-this-page"],
 }
 html_sidebars = {
@@ -188,6 +188,7 @@ html_context = {
         "latest": "devel (latest)",
         "stable": "current (stable)",
     },
+    "default_mode": "light",
 }
 
 # Options for LaTeX output
diff --git a/doc/reference/algorithms/polynomials.rst b/doc/reference/algorithms/polynomials.rst
index 0e1ec1598..d1409c6db 100644
--- a/doc/reference/algorithms/polynomials.rst
+++ b/doc/reference/algorithms/polynomials.rst
@@ -7,3 +7,4 @@ Graph Polynomials
    :toctree: generated/
 
    tutte_polynomial
+   chromatic_polynomial
diff --git a/networkx/algorithms/components/biconnected.py b/networkx/algorithms/components/biconnected.py
index 390a4924f..1eebe8ad2 100644
--- a/networkx/algorithms/components/biconnected.py
+++ b/networkx/algorithms/components/biconnected.py
@@ -75,15 +75,20 @@ def is_biconnected(G):
        Communications of the ACM 16: 372–378. doi:10.1145/362248.362272
 
     """
-    bcc = list(biconnected_components(G))
-    if len(bcc) == 1:
-        return len(bcc[0]) == len(G)
-    return False  # Multiple bicomponents or No bicomponents (empty graph?)
-
-
-#    if len(bcc) == 0:  # No bicomponents (it could be an empty graph)
-#        return False
-#    return len(bcc[0]) == len(G)
+    bccs = biconnected_components(G)
+    try:
+        bcc = next(bccs)
+    except StopIteration:
+        # No bicomponents (empty graph?)
+        return False
+    try:
+        next(bccs)
+    except StopIteration:
+        # Only one bicomponent
+        return len(bcc) == len(G)
+    else:
+        # Multiple bicomponents
+        return False
 
 
 @not_implemented_for("directed")
diff --git a/networkx/algorithms/cycles.py b/networkx/algorithms/cycles.py
index f3a2b9ca8..48d32ae09 100644
--- a/networkx/algorithms/cycles.py
+++ b/networkx/algorithms/cycles.py
@@ -111,28 +111,26 @@ def simple_cycles(G):
     G : NetworkX DiGraph
        A directed graph
 
-    Returns
-    -------
-    cycle_generator: generator
-       A generator that produces elementary cycles of the graph.
+    Yields
+    ------
+    list of nodes
        Each cycle is represented by a list of nodes along the cycle.
 
     Examples
     --------
     >>> edges = [(0, 0), (0, 1), (0, 2), (1, 2), (2, 0), (2, 1), (2, 2)]
     >>> G = nx.DiGraph(edges)
-    >>> len(list(nx.simple_cycles(G)))
-    5
+    >>> sorted(nx.simple_cycles(G))
+    [[0], [0, 1, 2], [0, 2], [1, 2], [2]]
 
     To filter the cycles so that they don't include certain nodes or edges,
-    copy your graph and eliminate those nodes or edges before calling
-
-    >>> copyG = G.copy()
-    >>> copyG.remove_nodes_from([1])
-    >>> copyG.remove_edges_from([(0, 1)])
-    >>> len(list(nx.simple_cycles(copyG)))
-    3
+    copy your graph and eliminate those nodes or edges before calling.
+    For example, to exclude self-loops from the above example:
 
+    >>> H = G.copy()
+    >>> H.remove_edges_from(nx.selfloop_edges(G))
+    >>> sorted(nx.simple_cycles(H))
+    [[0, 1, 2], [0, 2], [1, 2]]
 
     Notes
     -----
diff --git a/networkx/algorithms/distance_measures.py b/networkx/algorithms/distance_measures.py
index 68e8dc69e..3f59a2a32 100644
--- a/networkx/algorithms/distance_measures.py
+++ b/networkx/algorithms/distance_measures.py
@@ -52,7 +52,9 @@ def extrema_bounding(G, compute="diameter"):
     NetworkXError
         If the graph consists of multiple components
     ValueError
-        If `compute` is not one of "diameter", "radius", "periphery", "center", or "eccentricities".
+        If `compute` is not one of "diameter", "radius", "periphery", "center",
+        or "eccentricities".
+
     Notes
     -----
     This algorithm was proposed in the following papers:
diff --git a/networkx/algorithms/polynomials.py b/networkx/algorithms/polynomials.py
index a3b80f31b..35c0166ef 100644
--- a/networkx/algorithms/polynomials.py
+++ b/networkx/algorithms/polynomials.py
@@ -13,13 +13,13 @@ from collections import deque
 import networkx as nx
 from networkx.utils import not_implemented_for
 
-__all__ = ["tutte_polynomial"]
+__all__ = ["tutte_polynomial", "chromatic_polynomial"]
 
 
 @not_implemented_for("directed")
 def tutte_polynomial(G):
     r"""Returns the Tutte polynomial of `G`
-    
+
     This function computes the Tutte polynomial via an iterative version of
     the deletion-contraction algorithm.
 
@@ -163,3 +163,128 @@ def tutte_polynomial(G):
             stack.append(G)
             stack.append(C)
     return sympy.simplify(polynomial)
+
+
+@not_implemented_for("directed")
+def chromatic_polynomial(G):
+    r"""Returns the chromatic polynomial of `G`
+
+    This function computes the chromatic polynomial via an iterative version of
+    the deletion-contraction algorithm.
+
+    The chromatic polynomial `X_G(x)` is a fundamental graph polynomial
+    invariant in one variable. Evaluating `X_G(k)` for an natural number `k`
+    enumerates the proper k-colorings of `G`.
+
+    There are several equivalent definitions; here are three:
+
+    Def 1 (explicit formula):
+    For `G` an undirected graph, `c(G)` the number of connected components of
+    `G`, `E` the edge set of `G`, and `G(S)` the spanning subgraph of `G` with
+    edge set `S` [1]_:
+
+    .. math::
+
+        X_G(x) = \sum_{S \subseteq E} (-1)^{|S|} x^{c(G(S))}
+
+
+    Def 2 (interpolating polynomial):
+    For `G` an undirected graph, `n(G)` the number of vertices of `G`, `k_0 = 0`,
+    and `k_i` the number of distinct ways to color the vertices of `G` with `i`
+    unique colors (for `i` a natural number at most `n(G)`), `X_G(x)` is the
+    unique Lagrange interpolating polynomial of degree `n(G)` through the points
+    `(0, k_0), (1, k_1), \dots, (n(G), k_{n(G)})` [2]_.
+
+
+    Def 3 (chromatic recurrence):
+    For `G` an undirected graph, `G-e` the graph obtained from `G` by deleting
+    edge `e`, `G/e` the graph obtained from `G` by contracting edge `e`, `n(G)`
+    the number of vertices of `G`, and `e(G)` the number of edges of `G` [3]_:
+
+    .. math::
+        X_G(x) = \begin{cases}
+    	   x^{n(G)}, & \text{if $e(G)=0$} \\
+           X_{G-e}(x) - X_{G/e}(x), & \text{otherwise, for an arbitrary edge $e$}
+        \end{cases}
+
+    This formulation is also known as the Fundamental Reduction Theorem [4]_.
+
+
+    Parameters
+    ----------
+    G : NetworkX graph
+
+    Returns
+    -------
+    instance of `sympy.core.add.Add`
+        A Sympy expression representing the chromatic polynomial for `G`.
+
+    Examples
+    --------
+    >>> C = nx.cycle_graph(5)
+    >>> nx.chromatic_polynomial(C)
+    x**5 - 5*x**4 + 10*x**3 - 10*x**2 + 4*x
+
+    >>> G = nx.complete_graph(4)
+    >>> nx.chromatic_polynomial(G)
+    x**4 - 6*x**3 + 11*x**2 - 6*x
+
+    Notes
+    -----
+    Interpretation of the coefficients is discussed in [5]_. Several special
+    cases are listed in [2]_.
+
+    The chromatic polynomial is a specialization of the Tutte polynomial; in
+    particular, `X_G(x) = `T_G(x, 0)` [6]_.
+
+    The chromatic polynomial may take negative arguments, though evaluations
+    may not have chromatic interpretations. For instance, `X_G(-1)` enumerates
+    the acyclic orientations of `G` [7]_.
+
+    References
+    ----------
+    .. [1] D. B. West,
+       "Introduction to Graph Theory," p. 222
+    .. [2] E. W. Weisstein
+       "Chromatic Polynomial"
+       MathWorld--A Wolfram Web Resource
+       https://mathworld.wolfram.com/ChromaticPolynomial.html
+    .. [3] D. B. West,
+       "Introduction to Graph Theory," p. 221
+    .. [4] J. Zhang, J. Goodall,
+       "An Introduction to Chromatic Polynomials"
+       https://math.mit.edu/~apost/courses/18.204_2018/Julie_Zhang_paper.pdf
+    .. [5] R. C. Read,
+       "An Introduction to Chromatic Polynomials"
+       Journal of Combinatorial Theory, 1968
+       https://math.berkeley.edu/~mrklug/ReadChromatic.pdf
+    .. [6] W. T. Tutte,
+       "Graph-polynomials"
+       Advances in Applied Mathematics, 2004
+       https://www.sciencedirect.com/science/article/pii/S0196885803000411
+    .. [7] R. P. Stanley,
+       "Acyclic orientations of graphs"
+       Discrete Mathematics, 2006
+       https://math.mit.edu/~rstan/pubs/pubfiles/18.pdf
+    """
+    import sympy
+
+    x = sympy.Symbol("x")
+    stack = deque()
+    stack.append(nx.MultiGraph(G, contraction_idx=0))
+
+    polynomial = 0
+    while stack:
+        G = stack.pop()
+        edges = list(G.edges)
+        if not edges:
+            polynomial += (-1) ** G.graph["contraction_idx"] * x ** len(G)
+        else:
+            e = edges[0]
+            C = nx.contracted_edge(G, e, self_loops=True)
+            C.graph["contraction_idx"] = G.graph["contraction_idx"] + 1
+            C.remove_edge(e[0], e[0])
+            G.remove_edge(*e)
+            stack.append(G)
+            stack.append(C)
+    return polynomial
diff --git a/networkx/classes/multidigraph.py b/networkx/classes/multidigraph.py
index eea17ff11..69f77ff36 100644
--- a/networkx/classes/multidigraph.py
+++ b/networkx/classes/multidigraph.py
@@ -504,7 +504,9 @@ class MultiDiGraph(MultiGraph, DiGraph):
             Remove an edge between nodes u and v.
         key : hashable identifier, optional (default=None)
             Used to distinguish multiple edges between a pair of nodes.
-            If None remove a single (arbitrary) edge between u and v.
+            If None, remove a single edge between u and v. If there are
+            multiple edges, removes the last edge added in terms of
+            insertion order.
 
         Raises
         ------
@@ -529,7 +531,13 @@ class MultiDiGraph(MultiGraph, DiGraph):
         >>> G = nx.MultiDiGraph()
         >>> G.add_edges_from([(1, 2), (1, 2), (1, 2)])  # key_list returned
         [0, 1, 2]
-        >>> G.remove_edge(1, 2)  # remove a single (arbitrary) edge
+
+        When ``key=None`` (the default), edges are removed in the opposite
+        order that they were added:
+
+        >>> G.remove_edge(1, 2)
+        >>> G.edges(keys=True)
+        OutMultiEdgeView([(1, 2, 0), (1, 2, 1)])
 
         For edges with keys
 
@@ -538,7 +546,9 @@ class MultiDiGraph(MultiGraph, DiGraph):
         'first'
         >>> G.add_edge(1, 2, key="second")
         'second'
-        >>> G.remove_edge(1, 2, key="second")
+        >>> G.remove_edge(1, 2, key="first")
+        >>> G.edges(keys=True)
+        OutMultiEdgeView([(1, 2, 'second')])
 
         """
         try:
diff --git a/networkx/classes/multigraph.py b/networkx/classes/multigraph.py
index e3488be44..2757aae34 100644
--- a/networkx/classes/multigraph.py
+++ b/networkx/classes/multigraph.py
@@ -596,7 +596,9 @@ class MultiGraph(Graph):
             Remove an edge between nodes u and v.
         key : hashable identifier, optional (default=None)
             Used to distinguish multiple edges between a pair of nodes.
-            If None remove a single (arbitrary) edge between u and v.
+            If None, remove a single edge between u and v. If there are
+            multiple edges, removes the last edge added in terms of
+            insertion order.
 
         Raises
         ------
@@ -621,17 +623,27 @@ class MultiGraph(Graph):
         >>> G = nx.MultiGraph()  # or MultiDiGraph, etc
         >>> G.add_edges_from([(1, 2), (1, 2), (1, 2)])  # key_list returned
         [0, 1, 2]
-        >>> G.remove_edge(1, 2)  # remove a single (arbitrary) edge
+
+        When ``key=None`` (the default), edges are removed in the opposite
+        order that they were added:
+
+        >>> G.remove_edge(1, 2)
+        >>> G.edges(keys=True)
+        MultiEdgeView([(1, 2, 0), (1, 2, 1)])
         >>> G.remove_edge(2, 1)  # edges are not directed
+        >>> G.edges(keys=True)
+        MultiEdgeView([(1, 2, 0)])
 
         For edges with keys
 
-        >>> G = nx.MultiGraph()  # or MultiDiGraph, etc
+        >>> G = nx.MultiGraph()
         >>> G.add_edge(1, 2, key="first")
         'first'
         >>> G.add_edge(1, 2, key="second")
         'second'
-        >>> G.remove_edge(1, 2, key="second")
+        >>> G.remove_edge(1, 2, key="first")
+        >>> G.edges(keys=True)
+        MultiEdgeView([(1, 2, 'second')])
 
         """
         try:
@@ -662,7 +674,7 @@ class MultiGraph(Graph):
             Each edge given in the list or container will be removed
             from the graph. The edges can be:
 
-                - 2-tuples (u, v) All edges between u and v are removed.
+                - 2-tuples (u, v) A single edge between u and v is removed.
                 - 3-tuples (u, v, key) The edge identified by key is removed.
                 - 4-tuples (u, v, key, data) where data is ignored.
 
@@ -690,6 +702,20 @@ class MultiGraph(Graph):
         >>> G.remove_edges_from([(1, 2), (1, 2)])  # silently ignore extra copy
         >>> list(G.edges)  # now empty graph
         []
+
+        When the edge is a 2-tuple ``(u, v)`` but there are multiple edges between
+        u and v in the graph, the most recent edge (in terms of insertion
+        order) is removed.
+
+        >>> G = nx.MultiGraph()
+        >>> for key in ("x", "y", "a"):
+        ...     k = G.add_edge(0, 1, key=key)
+        >>> G.edges(keys=True)
+        MultiEdgeView([(0, 1, 'x'), (0, 1, 'y'), (0, 1, 'a')])
+        >>> G.remove_edges_from([(0, 1)])
+        >>> G.edges(keys=True)
+        MultiEdgeView([(0, 1, 'x'), (0, 1, 'y')])
+
         """
         for e in ebunch:
             try:
diff --git a/networkx/drawing/layout.py b/networkx/drawing/layout.py
index 23381a246..b6d2afe5d 100644
--- a/networkx/drawing/layout.py
+++ b/networkx/drawing/layout.py
@@ -1083,11 +1083,16 @@ def multipartite_layout(G, subset_key="subset", align="vertical", scale=1, cente
             raise ValueError(msg)
         layers[layer] = [v] + layers.get(layer, [])
 
+    # Sort by layer, if possible
+    try:
+        layers = sorted(layers.items())
+    except TypeError:
+        layers = list(layers.items())
+
     pos = None
     nodes = []
-
     width = len(layers)
-    for i, layer in enumerate(layers.values()):
+    for i, (_, layer) in enumerate(layers):
         height = len(layer)
         xs = np.repeat(i, height)
         ys = np.arange(0, height, dtype=float)
diff --git a/networkx/drawing/nx_pydot.py b/networkx/drawing/nx_pydot.py
index 7df22b9c6..bb933485e 100644
--- a/networkx/drawing/nx_pydot.py
+++ b/networkx/drawing/nx_pydot.py
@@ -169,6 +169,13 @@ def from_pydot(P):
     return N
 
 
+def _check_colon_quotes(s):
+    # A quick helper function to check if a string has a colon in it
+    # and if it is quoted properly with double quotes.
+    # refer https://github.com/pydot/pydot/issues/258
+    return ":" in s and (s[0] != '"' or s[-1] != '"')
+
+
 def to_pydot(N):
     """Returns a pydot graph from a NetworkX graph N.
 
@@ -213,25 +220,68 @@ def to_pydot(N):
         pass
 
     for n, nodedata in N.nodes(data=True):
-        str_nodedata = {k: str(v) for k, v in nodedata.items()}
-        p = pydot.Node(str(n), **str_nodedata)
-        # Explicitly catch all node name parsing errors
-        if len(str(n)) != len(p.get_name()):
+        str_nodedata = {str(k): str(v) for k, v in nodedata.items()}
+        # Explicitly catch nodes with ":" in node names or nodedata.
+        n = str(n)
+        raise_error = _check_colon_quotes(n) or (
+            any(
+                (_check_colon_quotes(k) or _check_colon_quotes(v))
+                for k, v in str_nodedata.items()
+            )
+        )
+        if raise_error:
             raise ValueError(
-                f"{str(n)} is not a valid node name while using pydot. Please refer https://github.com/pydot/pydot/issues/258"
+                f'Node names and attributes should not contain ":" unless they are quoted with "".\
+                For example the string \'attribute:data1\' should be written as \'"attribute:data1"\'.\
+                Please refer https://github.com/pydot/pydot/issues/258'
             )
+        p = pydot.Node(n, **str_nodedata)
         P.add_node(p)
 
     if N.is_multigraph():
         for u, v, key, edgedata in N.edges(data=True, keys=True):
-            str_edgedata = {k: str(v) for k, v in edgedata.items() if k != "key"}
-            edge = pydot.Edge(str(u), str(v), key=str(key), **str_edgedata)
+            str_edgedata = {str(k): str(v) for k, v in edgedata.items() if k != "key"}
+            u, v = str(u), str(v)
+            raise_error = (
+                _check_colon_quotes(u)
+                or _check_colon_quotes(v)
+                or (
+                    any(
+                        (_check_colon_quotes(k) or _check_colon_quotes(v))
+                        for k, v in edgedata.items()
+                    )
+                )
+            )
+            if raise_error:
+                raise ValueError(
+                    f'Node names and attributes should not contain ":" unless they are quoted with "".\
+                    For example the string \'attribute:data1\' should be written as \'"attribute:data1"\'.\
+                    Please refer https://github.com/pydot/pydot/issues/258'
+                )
+            edge = pydot.Edge(u, v, key=str(key), **str_edgedata)
             P.add_edge(edge)
 
     else:
         for u, v, edgedata in N.edges(data=True):
             str_edgedata = {k: str(v) for k, v in edgedata.items()}
-            edge = pydot.Edge(str(u), str(v), **str_edgedata)
+            u, v = str(u), str(v)
+            raise_error = (
+                _check_colon_quotes(u)
+                or _check_colon_quotes(v)
+                or (
+                    any(
+                        (_check_colon_quotes(k) or _check_colon_quotes(v))
+                        for k, v in edgedata.items()
+                    )
+                )
+            )
+            if raise_error:
+                raise ValueError(
+                    f'Node names and attributes should not contain ":" unless they are quoted with "".\
+                    For example the string \'attribute:data1\' should be written as \'"attribute:data1"\'.\
+                    Please refer https://github.com/pydot/pydot/issues/258'
+                )
+            edge = pydot.Edge(u, v, **str_edgedata)
             P.add_edge(edge)
     return P
 
@@ -338,12 +388,15 @@ def pydot_layout(G, prog="neato", root=None):
 
     node_pos = {}
     for n in G.nodes():
-        pydot_node = pydot.Node(str(n)).get_name()
-        # Explicitly catch all node name parsing errors
-        if len(str(n)) != len(pydot_node):
+        n = str(n)
+        # Explicitly catch nodes with ":" in node names or nodedata.
+        if _check_colon_quotes(n):
             raise ValueError(
-                f"{str(n)} is not a valid node name while using pydot. Please refer https://github.com/pydot/pydot/issues/258"
+                f'Node names and node attributes should not contain ":" unless they are quoted with "".\
+                For example the string \'attribute:data1\' should be written as \'"attribute:data1"\'.\
+                Please refer https://github.com/pydot/pydot/issues/258'
             )
+        pydot_node = pydot.Node(n).get_name()
         node = Q.get_node(pydot_node)
 
         if isinstance(node, list):


Test patch:
diff --git a/.github/workflows/test.yml b/.github/workflows/test.yml
index 5b267cc70..fb073d3f5 100644
--- a/.github/workflows/test.yml
+++ b/.github/workflows/test.yml
@@ -26,9 +26,7 @@ jobs:
 
     - name: Test NetworkX
       run: |
-        # NOTE: --assert=plain necessary to work around known pytest issue.
-        # See pytest-dev/pytest#10008
-        pytest --durations=10 --pyargs --assert=plain networkx
+        pytest --durations=10 --pyargs networkx
 
   default:
     runs-on: ${{ matrix.os }}-latest
diff --git a/networkx/algorithms/tests/test_polynomials.py b/networkx/algorithms/tests/test_polynomials.py
index 41f5d6000..a81d6a695 100644
--- a/networkx/algorithms/tests/test_polynomials.py
+++ b/networkx/algorithms/tests/test_polynomials.py
@@ -8,21 +8,29 @@ sympy = pytest.importorskip("sympy")
 
 
 # Mapping of input graphs to a string representation of their tutte polynomials
-_test_graphs = {
+_test_tutte_graphs = {
     nx.complete_graph(1): "1",
     nx.complete_graph(4): "x**3 + 3*x**2 + 4*x*y + 2*x + y**3 + 3*y**2 + 2*y",
     nx.cycle_graph(5): "x**4 + x**3 + x**2 + x + y",
     nx.diamond_graph(): "x**3 + 2*x**2 + 2*x*y + x + y**2 + y",
 }
 
+_test_chromatic_graphs = {
+    nx.complete_graph(1): "x",
+    nx.complete_graph(4): "x**4 - 6*x**3 + 11*x**2 - 6*x",
+    nx.cycle_graph(5): "x**5 - 5*x**4 + 10*x**3 - 10*x**2 + 4*x",
+    nx.diamond_graph(): "x**4 - 5*x**3 + 8*x**2 - 4*x",
+    nx.path_graph(5): "x**5 - 4*x**4 + 6*x**3 - 4*x**2 + x",
+}
+
 
-@pytest.mark.parametrize(("G", "expected"), _test_graphs.items())
+@pytest.mark.parametrize(("G", "expected"), _test_tutte_graphs.items())
 def test_tutte_polynomial(G, expected):
-    assert str(nx.tutte_polynomial(G)) == expected
+    assert nx.tutte_polynomial(G).equals(expected)
 
 
-@pytest.mark.parametrize("G", _test_graphs.keys())
-def test_tutte_polynomial_disjoint_K1(G):
+@pytest.mark.parametrize("G", _test_tutte_graphs.keys())
+def test_tutte_polynomial_disjoint(G):
     """Tutte polynomial factors into the Tutte polynomials of its components.
     Verify this property with the disjoint union of two copies of the input graph.
     """
@@ -30,3 +38,20 @@ def test_tutte_polynomial_disjoint_K1(G):
     H = nx.disjoint_union(G, G)
     t_h = nx.tutte_polynomial(H)
     assert sympy.simplify(t_g * t_g).equals(t_h)
+
+
+@pytest.mark.parametrize(("G", "expected"), _test_chromatic_graphs.items())
+def test_chromatic_polynomial(G, expected):
+    assert nx.chromatic_polynomial(G).equals(expected)
+
+
+@pytest.mark.parametrize("G", _test_chromatic_graphs.keys())
+def test_chromatic_polynomial_disjoint(G):
+    """Chromatic polynomial factors into the Chromatic polynomials of its
+    components. Verify this property with the disjoint union of two copies of
+    the input graph.
+    """
+    x_g = nx.chromatic_polynomial(G)
+    H = nx.disjoint_union(G, G)
+    x_h = nx.chromatic_polynomial(H)
+    assert sympy.simplify(x_g * x_g).equals(x_h)
diff --git a/networkx/classes/tests/test_subgraphviews.py b/networkx/classes/tests/test_subgraphviews.py
index 9d938c0c5..63c513646 100644
--- a/networkx/classes/tests/test_subgraphviews.py
+++ b/networkx/classes/tests/test_subgraphviews.py
@@ -1,6 +1,7 @@
 import pytest
 
 import networkx as nx
+from networkx.utils import edges_equal
 
 
 class TestSubGraphView:
@@ -292,7 +293,9 @@ class TestEdgeSubGraph:
 
     def test_correct_edges(self):
         """Tests that the subgraph has the correct edges."""
-        assert [(0, 1, "edge01"), (3, 4, "edge34")] == sorted(self.H.edges.data("name"))
+        assert edges_equal(
+            [(0, 1, "edge01"), (3, 4, "edge34")], self.H.edges.data("name")
+        )
 
     def test_add_node(self):
         """Tests that adding a node to the original graph does not
@@ -310,6 +313,7 @@ class TestEdgeSubGraph:
         """
         self.G.remove_node(0)
         assert [1, 3, 4] == sorted(self.H.nodes)
+        self.G.add_node(0, name="node0")
         self.G.add_edge(0, 1, name="edge01")
 
     def test_node_attr_dict(self):
diff --git a/networkx/drawing/tests/test_layout.py b/networkx/drawing/tests/test_layout.py
index f2fd90e71..f24d00381 100644
--- a/networkx/drawing/tests/test_layout.py
+++ b/networkx/drawing/tests/test_layout.py
@@ -422,3 +422,24 @@ def test_multipartite_layout_nonnumeric_partition_labels():
     G.add_edges_from([(0, 2), (0, 3), (1, 2)])
     pos = nx.multipartite_layout(G)
     assert len(pos) == len(G)
+
+
+def test_multipartite_layout_layer_order():
+    """Return the layers in sorted order if the layers of the multipartite
+    graph are sortable. See gh-5691"""
+    G = nx.Graph()
+    for node, layer in zip(("a", "b", "c", "d", "e"), (2, 3, 1, 2, 4)):
+        G.add_node(node, subset=layer)
+
+    # Horizontal alignment, therefore y-coord determines layers
+    pos = nx.multipartite_layout(G, align="horizontal")
+
+    # Nodes "a" and "d" are in the same layer
+    assert pos["a"][-1] == pos["d"][-1]
+    # positions should be sorted according to layer
+    assert pos["c"][-1] < pos["a"][-1] < pos["b"][-1] < pos["e"][-1]
+
+    # Make sure that multipartite_layout still works when layers are not sortable
+    G.nodes["a"]["subset"] = "layer_0"  # Can't sort mixed strs/ints
+    pos_nosort = nx.multipartite_layout(G)  # smoke test: this should not raise
+    assert pos_nosort.keys() == pos.keys()
diff --git a/networkx/drawing/tests/test_pydot.py b/networkx/drawing/tests/test_pydot.py
index 7d64635e0..134e0112e 100644
--- a/networkx/drawing/tests/test_pydot.py
+++ b/networkx/drawing/tests/test_pydot.py
@@ -98,12 +98,56 @@ class TestPydot:
         H = nx.nx_pydot.read_dot(fh)
         assert graphs_equal(G, H)
 
-    def test_pydot_issue_258(self):
-        G = nx.Graph([("Example:A", 1)])
-        with pytest.raises(ValueError):
-            nx.nx_pydot.to_pydot(G)
-        with pytest.raises(ValueError):
-            nx.nx_pydot.pydot_layout(G)
-        G = nx.Graph([('"Example:A"', 1)])
-        layout = nx.nx_pydot.pydot_layout(G)
-        assert isinstance(layout, dict)
+
+def test_pydot_issue_258():
+    G = nx.Graph([("Example:A", 1)])
+    with pytest.raises(ValueError):
+        nx.nx_pydot.to_pydot(G)
+    with pytest.raises(ValueError):
+        nx.nx_pydot.pydot_layout(G)
+
+    G = nx.Graph()
+    G.add_node("1.2", style="filled", fillcolor="red:yellow")
+    with pytest.raises(ValueError):
+        nx.nx_pydot.to_pydot(G)
+    G.remove_node("1.2")
+    G.add_node("1.2", style="filled", fillcolor='"red:yellow"')
+    assert (
+        G.nodes.data() == nx.nx_pydot.from_pydot(nx.nx_pydot.to_pydot(G)).nodes.data()
+    )
+
+    G = nx.DiGraph()
+    G.add_edge("1", "2", foo="bar:1")
+    with pytest.raises(ValueError):
+        nx.nx_pydot.to_pydot(G)
+    G = nx.DiGraph()
+    G.add_edge("1", "2", foo='"bar:1"')
+    assert G["1"]["2"] == nx.nx_pydot.from_pydot(nx.nx_pydot.to_pydot(G))["1"]["2"]
+
+    G = nx.MultiGraph()
+    G.add_edge("1", "2", foo="b:1")
+    G.add_edge("1", "2", bar="foo:foo")
+    with pytest.raises(ValueError):
+        nx.nx_pydot.to_pydot(G)
+    G = nx.MultiGraph()
+    G.add_edge("1", "2", foo='"b:1"')
+    G.add_edge("1", "2", bar='"foo:foo"')
+    # Keys as integers aren't preserved in the conversion. They are read as strings.
+    assert [attr for _, _, attr in G.edges.data()] == [
+        attr
+        for _, _, attr in nx.nx_pydot.from_pydot(nx.nx_pydot.to_pydot(G)).edges.data()
+    ]
+
+    G = nx.Graph()
+    G.add_edge("1", "2")
+    G["1"]["2"]["f:oo"] = "bar"
+    with pytest.raises(ValueError):
+        nx.nx_pydot.to_pydot(G)
+    G = nx.Graph()
+    G.add_edge("1", "2")
+    G["1"]["2"]['"f:oo"'] = "bar"
+    assert G["1"]["2"] == nx.nx_pydot.from_pydot(nx.nx_pydot.to_pydot(G))["1"]["2"]
+
+    G = nx.Graph([('"Example:A"', 1)])
+    layout = nx.nx_pydot.pydot_layout(G)
+    assert isinstance(layout, dict)