Cycle lengths and chromatic number of graphs (Q1883263): Difference between revisions

Let \(r(G)\) and \(s(G)\) be the number of odd and even cycle lengths in a graph \(G,\) respectively. It is shown that for each graph \(G\) its chromatic number satisfies \(\chi (G)\leq \min \{2r(G)+2,2s(G)+3\}.\)

0 references

zbMATH Keywords

graph

0 references

chromatic number

0 references

cycle length

0 references

reviewed by

Peter Horák

0 references

MaRDI profile type

MaRDI publication profile

0 references

full work available at URL

https://doi.org/10.1016/j.disc.2003.11.055

0 references

cites work

Q5422499

0 references

Q3491635

0 references

Graphs with \(k\) odd cycle lengths

0 references

Q3433915

0 references

Colouring Graphs with Prescribed Induced Cycle Lengths

0 references

Identifiers

zbMATH Open document ID

1055.05060

0 references

DOI

10.1016/j.disc.2003.11.055

0 references

Mathematics Subject Classification ID

0 references

0 references

0 references

0 references

Sitelinks

Mathematics(1 entry)

mardi Publication:1883263

@@ Property / cites work @@
+Q5422499
@@ Property / cites work: Q5422499 / rank @@
+Normal rank
@@ Property / cites work @@
+Q3491635
@@ Property / cites work: Q3491635 / rank @@
+Normal rank
@@ Property / cites work @@
+Graphs with \(k\) odd cycle lengths
@@ Property / cites work: Graphs with \(k\) odd cycle lengths / rank @@
+Normal rank
@@ Property / cites work @@
+Q3433915
@@ Property / cites work: Q3433915 / rank @@
+Normal rank
@@ Property / cites work @@
+Colouring Graphs with Prescribed Induced Cycle Lengths
+Normal rank