Coloring the square of a planar graph
From MaRDI portal
Publication:4797924
DOI10.1002/jgt.10077zbMath1008.05065OpenAlexW4232151508MaRDI QIDQ4797924
Sean McGuinness, Jan van den Heuvel
Publication date: 10 March 2003
Published in: Journal of Graph Theory (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1002/jgt.10077
Planar graphs; geometric and topological aspects of graph theory (05C10) Coloring of graphs and hypergraphs (05C15) Graph labelling (graceful graphs, bandwidth, etc.) (05C78)
Related Items
\((d,1)\)-total labelling of planar graphs with large girth and high maximum degree ⋮ Optimal channel assignment and \(L(p,1)\)-labeling ⋮ List 2-distance \(\varDelta +3\)-coloring of planar graphs without 4,5-cycles ⋮ An improved bound on 2-distance coloring plane graphs with girth 5 ⋮ The List \(L(2, 1)\)-labeling of planar graphs ⋮ \(L(p,q)\)-labelling of \(K_{4}\)-minor free graphs ⋮ Light 3-stars in sparse plane graphs ⋮ Light and low 5-stars in normal plane maps with minimum degree 5 ⋮ Wegner's conjecture on 2-distance coloring ⋮ 2-distance coloring of a planar graph without 3, 4, 7-cycles ⋮ Wegner's conjecture on 2-distance coloring for planar graphs ⋮ On Radiocoloring Hierarchically Specified Planar Graphs: $$\mathcal{PSPACE}$$ -completeness and Approximations ⋮ Sharp upper bound of injective coloring of planar graphs with girth at least 5 ⋮ The \(L(2,1)\)-labeling on planar graphs ⋮ A note on additive choice number of planar graphs ⋮ Facial \(L(2, 1)\)-edge-labelings of trees ⋮ \(k-L(2,1)\)-labelling for planar graphs is NP-complete for \(k\geq 4\) ⋮ Low and light 5-stars in 3-polytopes with minimum degree 5 and restrictions on the degrees of major vertices ⋮ Describing \((d-2)\)-stars at \(d\)-vertices, \(d\leq 5\), in normal plane maps ⋮ Describing 4-stars at 5-vertices in normal plane maps with minimum degree 5 ⋮ 2-distance coloring of planar graphs with girth 5 ⋮ An optimal square coloring of planar graphs ⋮ Locally injective \(k\)-colourings of planar graphs ⋮ \(L(p,q)\)-labeling of a graph embeddable on the torus ⋮ Coloring the square of maximal Planar graphs with diameter two ⋮ Colouring a dominating set without conflicts: \(q\)-subset square colouring ⋮ Heights of minor 5-stars in 3-polytopes with minimum degree 5 and no vertices of degree 6 and 7 ⋮ L(2,1,1)-labeling of interval graphs ⋮ Low stars in normal plane maps with minimum degree 4 and no adjacent 4-vertices ⋮ Coloring the square of a \(K_{4}\)-minor free graph ⋮ Upper bounds on the linear chromatic number of a graph ⋮ Improved square coloring of planar graphs ⋮ Coloring squares of planar graphs with girth six ⋮ 2-distance coloring of planar graphs without adjacent 5-cycles ⋮ 2-Distance coloring of planar graphs without triangles and intersecting 4-cycles ⋮ Coloring squares of planar graphs with maximum degree at most five ⋮ 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 ⋮ A unified approach to distance-two colouring of graphs on surfaces ⋮ Distributed colorings for collision-free routing in sink-centric sensor networks ⋮ Soft 3-stars in sparse plane graphs ⋮ Randomly colouring graphs (a combinatorial view) ⋮ \(L(2,1)\)-labeling of oriented planar graphs ⋮ Linear choosability of graphs ⋮ Labelling of some planar graphs with a condition at distance two ⋮ Labeling planar graphs with a condition at distance two ⋮ Coloring the square of Sierpiński graphs ⋮ On the existence of specific stars in planar graphs ⋮ \(L(1,1)\)-labelling of the direct product of a complete graph and a cycle ⋮ NEIGHBOR SUM DISTINGUISHING COLORING OF SOME GRAPHS ⋮ Chromatic number of square of maximal outerplanar graphs ⋮ Labelling planar graphs without 4-cycles with a condition on distance two ⋮ A survey on the distance-colouring of graphs ⋮ An introduction to the discharging method via graph coloring ⋮ On 2-distance coloring of plane graphs with girth 5 ⋮ Upper bounds of \(r\)-hued colorings of planar graphs ⋮ On the \(L(p,1)\)-labelling of graphs ⋮ Low minor 5-stars in 3-polytopes with minimum degree 5 and no 6-vertices ⋮ New upper bounds on linear coloring of planar graphs ⋮ The distant-2 chromatic number of random proximity and random geometric graphs ⋮ New upper bounds on the \(L(2,1)\)-labeling of the skew and converse skew product graphs ⋮ Distance constrained labelings of planar graphs with no short cycles ⋮ A bound on the chromatic number of the square of a planar graph ⋮ The \(\Delta ^{2}\)-conjecture for \(L(2,1)\)-labelings is true for total graphs ⋮ Injective colorings of graphs with low average degree ⋮ The \(L(2,1)\)-labelling of trees ⋮ Coloring the square of the Cartesian product of two cycles ⋮ Minimum 2-distance coloring of planar graphs and channel assignment ⋮ 5-stars of low weight in normal plane maps with minimum degree 5 ⋮ List 2-distance coloring of planar graphs without short cycles ⋮ The list \(L(2,1)\)-labeling of planar graphs with large girth ⋮ Distance two surjective labelling of paths and interval graphs ⋮ Sufficient sparseness conditions for \(G^2\) to be \((\Delta + 1)\)-choosable, when \(\Delta \geq 5\) ⋮ The \(L(p, q)\)-labelling of planar graphs without 4-cycles ⋮ Subexponential algorithms for variants of the homomorphism problem in string graphs ⋮ \( L ( 2 , 1 )\)-labeling of disk intersection graphs ⋮ List‐Coloring the Squares of Planar Graphs without 4‐Cycles and 5‐Cycles ⋮ 2-Distance Coloring of Planar Graphs without 4-Cycles and 5-Cycles ⋮ Some results on distance two labelling of outerplanar graphs ⋮ \(2\)-distance coloring of planar graphs with maximum degree \(5\) ⋮ \(L(p, q)\)-labeling of planar graphs with small girth ⋮ Acyclic edge colorings of planar graphs and series parallel graphs ⋮ \(\lambda \)-backbone colorings along pairwise disjoint stars and matchings ⋮ Distance constrained labelings of \(K_{4}\)-minor free graphs ⋮ Optimal frequency assignment and planar list \(L(2, 1)\)-labeling ⋮ Angular Resolutions: Around Vertices and Crossings ⋮ 2-Distance chromatic number of some graph products ⋮ Coloring a dominating set without conflicts: \(q\)-subset square coloring ⋮ 2-Distance coloring of planar graph ⋮ 2-distance colorings of some direct products of paths and cycles ⋮ Linear-time algorithms for tree root problems ⋮ 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
Cites Work
This page was built for publication: Coloring the square of a planar graph
