Repository: networkx/networkx

Issue:
Can't retrieve all edges for pair of nodes in Multi(Di)Graph
<!--- Provide a general summary of the issue in the Title above -->
According to the docs, I should be able to subscript into Multi(Di)Graph by pair of nodes and retrieve all the edges:

> Hence, **G.edges[u, v]['color']** provides the value of the color attribute for edge (u, v) while for (u, v, c) in G.edges(data='color', default='red'): iterates through all the edges yielding the color attribute. [Docs](https://networkx.org/documentation/stable/reference/classes/generated/networkx.MultiGraph.edges.html)

Either the docs are incorrect (I suspect a copy-paste from non-Multi Graph/DiGraph), or this does not work as expected.

### Current Behavior
<!--- Tell us what happens instead of the expected behavior -->
```python
G = nx.MultiGraph()  # or MultiDiGraph
nx.add_path(G, [0, 1, 2])
key = G.add_edge(1, 2, weight=5)
G.edges[1, 2]
# G.edges[1, 2, 0] or G.edges[1, 2, 1] works
```

> ValueError: not enough values to unpack (expected 3, got 2)

### Expected Behavior
<!--- Tell us what should happen -->

I would expect to be able to retrieve all the (multi-)edges for a pair of nodes by subscripting into the edges of the MultiGraph:
```python
G.edges[1, 2]
```

> MultiEdgeView([(1, 2, 0), (1, 2, 1)])

### Environment
<!--- Please provide details about your local environment -->
Python version: 3.8
NetworkX version: 2.6.1


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..e0f4dd478 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:
@@ -569,14 +579,14 @@ class MultiDiGraph(MultiGraph, DiGraph):
         as well as edge attribute lookup. When called, it also provides
         an EdgeDataView object which allows control of access to edge
         attributes (but does not provide set-like operations).
-        Hence, `G.edges[u, v, k]['color']` provides the value of the color
-        attribute for edge from `u` to `v` with key `k` while
-        `for (u, v, k, c) in G.edges(data='color', default='red',
-        keys=True):` iterates through all the edges yielding the color
-        attribute with default `'red'` if no color attribute exists.
+        Hence, ``G.edges[u, v, k]['color']`` provides the value of the color
+        attribute for the edge from ``u`` to ``v`` with key ``k`` while
+        ``for (u, v, k, c) in G.edges(data='color', default='red', keys=True):``
+        iterates through all the edges yielding the color attribute with
+        default `'red'` if no color attribute exists.
 
         Edges are returned as tuples with optional data and keys
-        in the order (node, neighbor, key, data). If `keys=True` is not
+        in the order (node, neighbor, key, data). If ``keys=True`` is not
         provided, the tuples will just be (node, neighbor, data), but
         multiple tuples with the same node and neighbor will be
         generated when multiple edges between two nodes exist.
@@ -599,10 +609,10 @@ class MultiDiGraph(MultiGraph, DiGraph):
 
         Returns
         -------
-        edges : EdgeView
+        edges : OutMultiEdgeView
             A view of edge attributes, usually it iterates over (u, v)
             (u, v, k) or (u, v, k, d) tuples of edges, but can also be
-            used for attribute lookup as `edges[u, v, k]['foo']`.
+            used for attribute lookup as ``edges[u, v, k]['foo']``.
 
         Notes
         -----
diff --git a/networkx/classes/multigraph.py b/networkx/classes/multigraph.py
index e3488be44..6a01107da 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:
@@ -763,17 +789,21 @@ class MultiGraph(Graph):
 
         edges(self, nbunch=None, data=False, keys=False, default=None)
 
-        The EdgeView provides set-like operations on the edge-tuples
+        The MultiEdgeView provides set-like operations on the edge-tuples
         as well as edge attribute lookup. When called, it also provides
         an EdgeDataView object which allows control of access to edge
         attributes (but does not provide set-like operations).
-        Hence, `G.edges[u, v, k]['color']` provides the value of the color
-        attribute for edge `(u, v, k)` while
-        `for (u, v, c) in G.edges(data='color', default='red'):`
-        iterates through all the edges yielding the color attribute.
+        Hence, ``G.edges[u, v, k]['color']`` provides the value of the color
+        attribute for the edge from ``u`` to ``v`` with key ``k`` while
+        ``for (u, v, k, c) in G.edges(data='color', keys=True, default="red"):``
+        iterates through all the edges yielding the color attribute with
+        default `'red'` if no color attribute exists.
 
         Edges are returned as tuples with optional data and keys
-        in the order (node, neighbor, key, data).
+        in the order (node, neighbor, key, data). If ``keys=True`` is not
+        provided, the tuples will just be (node, neighbor, data), but
+        multiple tuples with the same node and neighbor will be generated
+        when multiple edges exist between two nodes.
 
         Parameters
         ----------
@@ -795,7 +825,7 @@ class MultiGraph(Graph):
         edges : MultiEdgeView
             A view of edge attributes, usually it iterates over (u, v)
             (u, v, k) or (u, v, k, d) tuples of edges, but can also be
-            used for attribute lookup as `edges[u, v, k]['foo']`.
+            used for attribute lookup as ``edges[u, v, k]['foo']``.
 
         Notes
         -----
@@ -804,7 +834,7 @@ class MultiGraph(Graph):
 
         Examples
         --------
-        >>> G = nx.MultiGraph()  # or MultiDiGraph
+        >>> G = nx.MultiGraph()
         >>> nx.add_path(G, [0, 1, 2])
         >>> key = G.add_edge(2, 3, weight=5)
         >>> key2 = G.add_edge(2, 1, weight=2)  # multi-edge
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):
diff --git a/requirements/doc.txt b/requirements/doc.txt
index cf1761e6a..881e5e8c5 100644
--- a/requirements/doc.txt
+++ b/requirements/doc.txt
@@ -1,7 +1,7 @@
-sphinx>=4.5
-pydata-sphinx-theme>=0.8.1
+sphinx>=5
+pydata-sphinx-theme>=0.9
 sphinx-gallery>=0.10
-numpydoc>=1.3
+numpydoc>=1.4
 pillow>=9.1
 nb2plots>=0.6
 texext>=0.6.6


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)