The Chromatic Number of Graph Powers

DOI10.1017/S0963548301004965MaRDI QIDQ4330739zbMATH OpenOpenAlexFDO

Authors Noga Alon, Bojan Mohar

Publication date 25 August 2002

Published in Combinatorics, Probability and Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1017/s0963548301004965

zbMATH Keywords

chromatic numbergraph powers

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Coloring of graphs and hypergraphs (05C15)

Recommendations

• Coloring powers and girth
• New upper bound on the chromatic number of the square of a planar graph
• Upper bound on chromatic number of square graph of sparse graphs
• The distance coloring of graphs
• Coloring squares of planar graphs with maximum degree at most five

Cited in

(32)

• Coloring Powers of Chordal Graphs
• A new class of polynomials from the spectrum of a graph, and its application to bound the \(k\)-independence number
• Coloring powers and girth
• Injective colorings of sparse graphs
• Graceful colorings of graphs with maximum degree three
• Linear-time algorithms for tree root problems
• Locating chromatic number of powers of paths and cycles
• A characterization of graphs with regular distance-2 graphs
• Computation of certain domination numbers of collaboration graphs
• Clustering powers of sparse graphs
• Randomly colouring graphs (a combinatorial view)
• On coloring numbers of graph powers
• On the \(k\)-independence number of graphs
• Algebraic bounds for the independence and chromatic number of graph powers
• The \(b\)-chromatic number of powers of hypercube
• On colorings of graph fractional powers
• Complexity of finding graph roots with girth conditions
• Sharp upper bounds on the \(k\)-independence number in graphs with given minimum and maximum degree
• Distance labellings of Cayley graphs of semigroups
• Distance colouring without one cycle length
• A note on the chromatic number of the square of Kneser graph \(K(2 k + 1, k)\)
• A new approach to the chromatic number of the square of Kneser graph \(K(2k+1,k)\)
• Frugal, acyclic and star colourings of graphs
• Optimization of eigenvalue bounds for the independence and chromatic number of graph powers
• Exact square coloring of subcubic planar graphs
• Distance colouring without one cycle length
• Eigenvalue bounds for the quantum chromatic number of graph powers
• On the two largest distance eigenvalues of graph powers
• -binding functions for squares of convex bipartite graphs and partite testability for bipartite squares
• Coloring squares of planar graphs with girth six
• The chromatic number of squares of random graphs
• Acyclic and \(k\)-distance coloring of the grid

This page was built for publication: The Chromatic Number of Graph Powers

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