A critically chromatic graph

DOI10.1016/S0012-365X(96)00262-2MaRDI QIDQ1366769zbMATH OpenOpenAlexFDO

Authors Chong-Yun Chao

Publication date 22 January 1998

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0012-365x(96)00262-2

zbMATH Keywords

Cayley graphchrmatic numberconnectivitycritical graph

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Review text

A graph is edge-critical \(n\)-chromatic if its chromatic number equals \(n\), i.e. \(\chi(G)=n\), and \(\chi(G-e)=n-1\) for every edge \(e\) of \(G\). In the paper an edge-critical 4-chromatic 4-connected graph on 13 vertices is constructed, which solves a problem due to Dirac.

Recommendations

• On a question of Dirac on critical and vertex critical graphs
• Colour-critical graphs with few edges
• scientific article; zbMATH DE number 4154465
• Dense critical and vertex-critical graphs

Cites work

• In abstrakten Graphen vorhandene vollständige 4‐Graphen und ihre Unterteilungen
• On the Classification of Symmetric Graphs with a Prime Number of Vertices
• On uniquely 3-colorable graphs

Cited in

(10)

• A class of edge critical 4-chromatic graphs
• On uniquely \(3\)-colorable graphs. II
• Dense critical and vertex-critical graphs
• Finding the chromatic number by means of critical graphs
• scientific article; zbMATH DE number 4154465 (Why is no real title available?)
• Critically cochromatic graphs
• A Möbius-type gluing technique for obtaining edge-critical graphs
• On \(4\)-colorable robust critical graphs
• Edge 4-critical Koester graph of order 28
• An analogue of Dirac's theorem on circular super-critical graphs

This page was built for publication: A critically chromatic graph

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1366769)