Fdtxjr

Multi tool use

Non-trope happy ending?

What is the highest possible scrabble score for placing a single tile

Strong empirical falsification of quantum mechanics based on vacuum energy density?

Is there a way to have vectors outlined in a Vector Plot?

Why does AES have exactly 10 rounds for a 128-bit key, 12 for 192 bits and 14 for a 256-bit key size?

Why is the "ls" command showing permissions of files in a FAT32 partition?

What features enable the Su-25 Frogfoot to operate with such a wide variety of fuels?

How do you make your own symbol when Detexify fails?

C++ check if statement can be evaluated constexpr

Why do Radio Buttons not fill the entire outer circle?

How to preserve electronics (computers, iPads and phones) for hundreds of years

Delete multiple columns using awk or sed

Why does Carol not get rid of the Kree symbol on her suit when she changes its colours?

awk assign to multiple variables at once

How to draw a matrix with arrows in limited space

Which was the first story featuring espers?

Biological Blimps: Propulsion

What (the heck) is a Super Worm Equinox Moon?

Is this toilet slogan correct usage of the English language?

Does "he squandered his car on drink" sound natural?

Why is the Sun approximated as a black body at ~ 5800 K?

Are Captain Marvel's powers affected by Thanos breaking the Tesseract and claiming the stone?

How to convince somebody that he is fit for something else, but not this job?

When were female captains banned from Starfleet?

The chromatic number of a triangle-free graph.

If G is a graph such that $Delta(G) = 3$ then $chi'(G) le 4$Upper bound on $chi(G)$ for a triangle-free graphEdge chromatic number question (Graph theory)Problem in Chromatic NumberFind an example of a regular triangle-free $4$-chromatic graphGraph with chromatic index 1 billion more than max degree?A triangle-free, 6-chromatic graph with 44 verticesAny planar graph of maximum degree $4$ has chromatic number at most $4$.Prove that the chromatic number of a graph is the same as the maximum of the chromatic numbers its blocks.Total chromatic number bound implied by list coloring conjecture

6

1

$begingroup$

Let $G$ be a triangle-free graph. Prove that $$chi(G)leq3leftlceildfracDelta(G)+14rightrceil$$

What's the relationship between the chromatic number and the maximum degree of a triangle-free graph $G$. I got a hint that I could apply the Brook's Theorem but I have no clue where to start.

graph-theory

share|cite|improve this question

edited Mar 15 at 15:47

MarianD

1,4741616

asked May 20 '14 at 10:06

user137988user137988

675

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Note that (for $nge 3$) the inequality holds for every odd cycle that is not a triangle and that furthemore, a triangle-free graph is certainly not a complete graph.
  $endgroup$
  – Studentmath
  May 20 '14 at 11:29
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  @Studentmath: please elaborate. How does this help to show that e.g. a triangle-free graph with maximum degree 23 only requires 18 colors.
  $endgroup$
  – Leen Droogendijk
  May 20 '14 at 13:32
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  I still can't figure this out. Can anyone post an answer?
  $endgroup$
  – Josh Ng
  Mar 14 at 17:29
  

  
  
  
  

add a comment | 

6

1

$begingroup$

Let $G$ be a triangle-free graph. Prove that $$chi(G)leq3leftlceildfracDelta(G)+14rightrceil$$

What's the relationship between the chromatic number and the maximum degree of a triangle-free graph $G$. I got a hint that I could apply the Brook's Theorem but I have no clue where to start.

graph-theory

share|cite|improve this question

edited Mar 15 at 15:47

MarianD

1,4741616

asked May 20 '14 at 10:06

user137988user137988

675

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Note that (for $nge 3$) the inequality holds for every odd cycle that is not a triangle and that furthemore, a triangle-free graph is certainly not a complete graph.
  $endgroup$
  – Studentmath
  May 20 '14 at 11:29
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  @Studentmath: please elaborate. How does this help to show that e.g. a triangle-free graph with maximum degree 23 only requires 18 colors.
  $endgroup$
  – Leen Droogendijk
  May 20 '14 at 13:32
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  I still can't figure this out. Can anyone post an answer?
  $endgroup$
  – Josh Ng
  Mar 14 at 17:29
  

  
  
  
  

add a comment | 

$begingroup$

Let $G$ be a triangle-free graph. Prove that $$chi(G)leq3leftlceildfracDelta(G)+14rightrceil$$

What's the relationship between the chromatic number and the maximum degree of a triangle-free graph $G$. I got a hint that I could apply the Brook's Theorem but I have no clue where to start.

graph-theory

share|cite|improve this question

edited Mar 15 at 15:47

MarianD

1,4741616

asked May 20 '14 at 10:06

user137988user137988

675

$endgroup$

share|cite|improve this question

edited Mar 15 at 15:47

MarianD

1,4741616

asked May 20 '14 at 10:06

user137988user137988

675

share|cite|improve this question

edited Mar 15 at 15:47

MarianD

1,4741616

asked May 20 '14 at 10:06

user137988user137988

675

edited Mar 15 at 15:47

MarianD

1,4741616

edited Mar 15 at 15:47

MarianD

1,4741616

asked May 20 '14 at 10:06

user137988user137988

675

asked May 20 '14 at 10:06

user137988user137988

675

2 Answers
2

active

oldest

votes

3

+50

$begingroup$

First take a partition of $V$ into $k=lceil(Delta+1)/4rceil$ classes $V_1,dots,V_k$ that minimizes the number of monochromatic edges. Note $Delta<4k.$ By the pigeonhole principle, for each vertex $vin V_j,$ there is some class $V_i$ such that at most three of the at most $Delta$ neighbors of $v$ lie in $V_i.$ By minimality, putting $v$ in $V_i$ instead of $V_j$ cannot decrease the number of monochromatic edges, so $v$ has at most three neighbors in $V_j.$ In other words $Delta(G[V_j])leq 3$ for each $j.$

By Brooks' theorem and the triangle-free assumption, each $G[V_j]$ has a 3-coloring. Using disjoint color sets for each $V_j$ we get a $3k$-coloring of $G$ as required.

A history of this result is given in the introduction to "Chromatic number, girth and maximal degree" by B. Bollobás. Improving the bound is an open problem.

share|cite|improve this answer

edited Mar 17 at 18:37

answered Mar 15 at 15:25

DapDap

18.9k842

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Do you mean $k = left lceil(Delta + 1)/4right rceil$?
  $endgroup$
  – ensbana
  Mar 17 at 17:11
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  @ensbana: I did mean that, thank you
  $endgroup$
  – Dap
  Mar 17 at 18:37
  

  
  
  
  

add a comment | 

1

$begingroup$

Hint: If there exists a partition $V(G)$ into $k$ subsets $V_1,ldots,V_k$ such that $chi(G_i)leq ell$ for every $i$ (where $G_i$ is the subgraph of $G$ induced by $V_i$), then $chi(G)leq ell k$.

share|cite|improve this answer

answered May 21 '14 at 7:42

CasteelsCasteels

10k42234

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  I still can't figure this out. Could you elaborate? Thanks.
  $endgroup$
  – Josh Ng
  Mar 14 at 17:28
  

  
  
  
  

add a comment | 

Your Answer

StackExchange.ifUsing("editor", function ()
return StackExchange.using("mathjaxEditing", function ()
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix)
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
);
);
, "mathjax-editing");

StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "69"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);

else
createEditor();

);

function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader:
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
,
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);



);

draft saved

draft discarded

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name

Email

Required, but never shown

StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f802656%2fthe-chromatic-number-of-a-triangle-free-graph%23new-answer', 'question_page');

);

Post as a guest

Name

Email

Required, but never shown

3

+50

$begingroup$

First take a partition of $V$ into $k=lceil(Delta+1)/4rceil$ classes $V_1,dots,V_k$ that minimizes the number of monochromatic edges. Note $Delta<4k.$ By the pigeonhole principle, for each vertex $vin V_j,$ there is some class $V_i$ such that at most three of the at most $Delta$ neighbors of $v$ lie in $V_i.$ By minimality, putting $v$ in $V_i$ instead of $V_j$ cannot decrease the number of monochromatic edges, so $v$ has at most three neighbors in $V_j.$ In other words $Delta(G[V_j])leq 3$ for each $j.$

By Brooks' theorem and the triangle-free assumption, each $G[V_j]$ has a 3-coloring. Using disjoint color sets for each $V_j$ we get a $3k$-coloring of $G$ as required.

A history of this result is given in the introduction to "Chromatic number, girth and maximal degree" by B. Bollobás. Improving the bound is an open problem.

share|cite|improve this answer

edited Mar 17 at 18:37

answered Mar 15 at 15:25

DapDap

18.9k842

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Do you mean $k = left lceil(Delta + 1)/4right rceil$?
  $endgroup$
  – ensbana
  Mar 17 at 17:11
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  @ensbana: I did mean that, thank you
  $endgroup$
  – Dap
  Mar 17 at 18:37
  

  
  
  
  

add a comment | 

3

+50

$begingroup$

First take a partition of $V$ into $k=lceil(Delta+1)/4rceil$ classes $V_1,dots,V_k$ that minimizes the number of monochromatic edges. Note $Delta<4k.$ By the pigeonhole principle, for each vertex $vin V_j,$ there is some class $V_i$ such that at most three of the at most $Delta$ neighbors of $v$ lie in $V_i.$ By minimality, putting $v$ in $V_i$ instead of $V_j$ cannot decrease the number of monochromatic edges, so $v$ has at most three neighbors in $V_j.$ In other words $Delta(G[V_j])leq 3$ for each $j.$

By Brooks' theorem and the triangle-free assumption, each $G[V_j]$ has a 3-coloring. Using disjoint color sets for each $V_j$ we get a $3k$-coloring of $G$ as required.

A history of this result is given in the introduction to "Chromatic number, girth and maximal degree" by B. Bollobás. Improving the bound is an open problem.

share|cite|improve this answer

edited Mar 17 at 18:37

answered Mar 15 at 15:25

DapDap

18.9k842

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Do you mean $k = left lceil(Delta + 1)/4right rceil$?
  $endgroup$
  – ensbana
  Mar 17 at 17:11
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  @ensbana: I did mean that, thank you
  $endgroup$
  – Dap
  Mar 17 at 18:37
  

  
  
  
  

add a comment | 

$begingroup$

First take a partition of $V$ into $k=lceil(Delta+1)/4rceil$ classes $V_1,dots,V_k$ that minimizes the number of monochromatic edges. Note $Delta<4k.$ By the pigeonhole principle, for each vertex $vin V_j,$ there is some class $V_i$ such that at most three of the at most $Delta$ neighbors of $v$ lie in $V_i.$ By minimality, putting $v$ in $V_i$ instead of $V_j$ cannot decrease the number of monochromatic edges, so $v$ has at most three neighbors in $V_j.$ In other words $Delta(G[V_j])leq 3$ for each $j.$

By Brooks' theorem and the triangle-free assumption, each $G[V_j]$ has a 3-coloring. Using disjoint color sets for each $V_j$ we get a $3k$-coloring of $G$ as required.

A history of this result is given in the introduction to "Chromatic number, girth and maximal degree" by B. Bollobás. Improving the bound is an open problem.

share|cite|improve this answer

edited Mar 17 at 18:37

answered Mar 15 at 15:25

DapDap

18.9k842

$endgroup$

share|cite|improve this answer

edited Mar 17 at 18:37

answered Mar 15 at 15:25

DapDap

18.9k842

answered Mar 15 at 15:25

DapDap

18.9k842

answered Mar 15 at 15:25

DapDap

18.9k842

1

$begingroup$

Hint: If there exists a partition $V(G)$ into $k$ subsets $V_1,ldots,V_k$ such that $chi(G_i)leq ell$ for every $i$ (where $G_i$ is the subgraph of $G$ induced by $V_i$), then $chi(G)leq ell k$.

share|cite|improve this answer

answered May 21 '14 at 7:42

CasteelsCasteels

10k42234

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  I still can't figure this out. Could you elaborate? Thanks.
  $endgroup$
  – Josh Ng
  Mar 14 at 17:28
  

  
  
  
  

add a comment | 

1

$begingroup$

Hint: If there exists a partition $V(G)$ into $k$ subsets $V_1,ldots,V_k$ such that $chi(G_i)leq ell$ for every $i$ (where $G_i$ is the subgraph of $G$ induced by $V_i$), then $chi(G)leq ell k$.

share|cite|improve this answer

answered May 21 '14 at 7:42

CasteelsCasteels

10k42234

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  I still can't figure this out. Could you elaborate? Thanks.
  $endgroup$
  – Josh Ng
  Mar 14 at 17:28
  

  
  
  
  

add a comment | 

$begingroup$

Hint: If there exists a partition $V(G)$ into $k$ subsets $V_1,ldots,V_k$ such that $chi(G_i)leq ell$ for every $i$ (where $G_i$ is the subgraph of $G$ induced by $V_i$), then $chi(G)leq ell k$.

share|cite|improve this answer

answered May 21 '14 at 7:42

CasteelsCasteels

10k42234

$endgroup$

share|cite|improve this answer

answered May 21 '14 at 7:42

CasteelsCasteels

10k42234

answered May 21 '14 at 7:42

CasteelsCasteels

10k42234

answered May 21 '14 at 7:42

CasteelsCasteels

10k42234