A bound on the chromatic number of the square of a planar graph
From MaRDI portal
Publication:2485944
The well-known Wegner conjecture says that \(\chi(G^2)\leq \lceil{3\over 2}\Delta\rceil+ 1\), where \(G^2\) is the square of graph \(G\) with maximum vertex degree \(\Delta\geq 8\). The authors prove the following main results. (1) For a planar graph \(G\), \(\chi(G^2)\leq \lceil{5\over 3}\Delta\rceil+ 78\). (2) For a planar graph \(G\), if \(\Delta\geq 241\), then \(\chi(G^2)\leq\lceil{5\over 3}\Delta\rceil+ 25\). They show how to transform the proof into a colouring algorithm which uses at most \(\lceil{5\over 3}\Delta\rceil+ 78\) colours. Since there are \(O(n)\) iterations of the main procedure, the total running time of the algorithm would be \(O(n^2)\).
Recommendations
Cites work
- 25 pretty graph colouring problems
- A new bound on the cyclic chromatic number
- Coloring Powers of Planar Graphs
- Coloring the square of a planar graph
- Every planar map is four colorable
- Graph labeling and radio channel assignment
- scientific article; zbMATH DE number 1819633 (Why is no real title available?)
- scientific article; zbMATH DE number 1185300 (Why is no real title available?)
- scientific article; zbMATH DE number 1500531 (Why is no real title available?)
- scientific article; zbMATH DE number 881282 (Why is no real title available?)
- scientific article; zbMATH DE number 1439442 (Why is no real title available?)
- Labelling Graphs with a Condition at Distance 2
- On the $\lambda$-Number of $Q_n $ and Related Graphs
- The $L(2,1)$-Labeling Problem on Graphs
Cited in
(only showing first 100 items - show all)- List 2-distance \((\varDelta +2)\)-coloring of planar graphs with girth six
- Some results on distance two labelling of outerplanar graphs
- -backbone colorings along pairwise disjoint stars and matchings
- Injective colorings of planar graphs with few colors
- Distance constrained labelings of \(K_{4}\)-minor free graphs
- 2-distance \((\varDelta +2)\)-coloring of planar graphs with girth six and \(\varDelta \geq 18\)
- Coloring the square of a \(K_{4}\)-minor free graph
- Optimal channel assignment and \(L(p,1)\)-labeling
- List 2-distance \(\varDelta +3\)-coloring of planar graphs without 4,5-cycles
- The List L(2, 1)-labeling of planar graphs
- Injective coloring of some graph operations
- Facial \(L(2, 1)\)-edge-labelings of trees
- 2-distance coloring of planar graphs with girth 5
- On list r-hued coloring of planar graphs
- The square of a planar cubic graph is 7-colorable
- 3-dynamic coloring of planar triangulations
- An optimal square coloring of planar graphs
- The L(2,1)-labelling problem for cubic Cayley graphs on dihedral groups
- The complexity of frugal colouring
- The list \(L(2,1)\)-labeling of planar graphs with large girth
- Distance two surjective labelling of paths and interval graphs
- \(2\)-distance coloring of planar graphs with maximum degree \(5\)
- Optimal frequency assignment and planar list L(2, 1)-labeling
- A characterization of graphs with regular distance-2 graphs
- Wegner's conjecture on 2-distance coloring
- Wegner's conjecture on 2-distance coloring for planar graphs
- List 2-distance coloring of planar graphs with girth five
- Sharp upper bound of injective coloring of planar graphs with girth at least 5
- Graph \(r\)-hued colorings -- a survey
- A note on the chromatic number of the square of Kneser graph \(K(2 k + 1, k)\)
- 2-distance colorings of some direct products of paths and cycles
- Linear-time algorithms for tree root problems
- \((2,1)\)-total labeling of trees with large maximum degree
- A new sufficient condition for a tree \(T\) to have the \((2,1)\)-total number \(\Delta +1\)
- A new approach to the chromatic number of the square of Kneser graph \(K(2k+1,k)\)
- Coloring squares of planar graphs with girth six
- A unified approach to distance-two colouring of graphs on surfaces
- \(L(2,1)\)-labeling of oriented planar graphs
- Labeling planar graphs with a condition at distance two
- \((2,1)\)-total labelling of outerplanar graphs
- On the existence of specific stars in planar graphs
- Chromatic number of square of maximal outerplanar graphs
- A survey on the distance-colouring of graphs
- Coloring the square of an outerplanar graph
- On the \(L(p,1)\)-labelling of graphs
- The L(2,1)-labelling of trees
- Degeneracy and colorings of squares of planar graphs without 4-cycles
- Improved square coloring of planar graphs
- Coloring squares of planar graphs with maximum degree at most five
- Brooks-type theorem for \(r\)-hued coloring of graphs
- On L (p, q)-labelling of planar graphs without cycles of length four
- 2-distance choosability of planar graphs with a restriction for maximum degree
- List 2-distance coloring of planar graphs without short cycles
- New upper bound on the chromatic number of the square of a planar graph
- An upper bound of linear chromatic number of planar graphs
- An improved bound on 2-distance coloring plane graphs with girth 5
- Coloring the square of a sparse graph G with almost (G) colors
- 2-distance coloring of a planar graph without 3, 4, 7-cycles
- Distance Constrained Labelings of <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" altimg="si1.gif" overflow="scroll"><mml:msub><mml:mi>K</mml:mi><mml:mn>4</mml:mn></mml:msub></mml:math>-minor Free Graphs
- On Radiocoloring Hierarchically Specified Planar Graphs: $$\mathcal{PSPACE}$$ -completeness and Approximations
- List Colouring Squares of Planar Graphs
- Conflict-free colourings of graphs and hypergraphs
- Locally injective k-colourings of planar graphs
- L(p,q)-labeling of a graph embeddable on the torus
- On backbone coloring of graphs
- scientific article; zbMATH DE number 1982173 (Why is no real title available?)
- Coloring the square of a planar graph
- Coloring the square of Sierpiński graphs
- \(L(1,1)\)-labelling of the direct product of a complete graph and a cycle
- 2-distance coloring of planar graph
- 2-distance choice number of planar graphs with maximal degree no more than 4
- An introduction to the discharging method via graph coloring
- On 2-distance coloring of plane graphs with girth 5
- 2-distance coloring of planar graphs without 4-cycles and 5-cycles
- Injective \((\Delta + 1)\)-coloring of planar graphs with girth 6
- Injective colorings of graphs with low average degree
- 2-distance chromatic number of some graph products
- Injective coloring of planar graphs
- Finding cut-vertices in the square roots of a graph
- A sufficient condition for a tree to be \((\Delta+1)\)-\((2,1)\)-totally labelable
- Coloring the square of maximal Planar graphs with diameter two
- L(2,1,1)-labeling of interval graphs
- List injective colorings of planar graphs
- 2-distance coloring of planar graphs without adjacent 5-cycles
- 2-Distance coloring of planar graphs without triangles and intersecting 4-cycles
- The list \(r\)-hued coloring of \(K_{m, n}\)
- A note on 3-distance coloring of planar graphs
- Bounding clique size in squares of planar graphs
- Some results on 2-distance coloring of planar graphs with girth five
- Minimization of span in \(L(3,1)\)-labeling for a particular type of intersection graphs
- Relaxation of Wegner's planar graph conjecture for maximum degree 4
- Improved 2-distance coloring of planar graphs with maximum degree 5
- The 2-distance chromatic number of planar graphs without 3,4,8-cycles
- An improved bound for 2-distance coloring of planar graphs with girth six
- Counting circuit double covers
- On 2-distance ( 2 + 6)-coloring of planar graphs
- A note on the r-hued coloring of planar graphs
- List 2-distance coloring of planar graphs without 4- and 5-cycles
- 2-distance coloring of planar graphs without 4, 6-cycles
- List 2-distance coloring for planar graphs with short circle constraints
This page was built for publication: A bound on the chromatic number of the square of a planar graph
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2485944)
