- 1. feladat Ö M
Ha egy
G
gráf minden pontjának foka legfeljebb
k
, akkor
χ
G
≤
k
+
1
.
- 2. feladat Ö M
Bizonyítsuk be, hogy bármely
G
gráfra található olyan
V
G
=
V
1
∪
V
2
(
V
1
,
V
2
≠
∅
) partíció, melyre
Továbbá ha
G
nem teljes, akkor található egy olyan
V
G
=
V
1
∪
V
2
partíció, melyre
- 3. feladat Ö M
Igazoljuk a
χ
G
1
∪
G
2
≤
χ
G
1
⋅
χ
G
2
egyenlőtlenséget.
- 4. feladat Ö M
Tegyük fel, hogy
G
-nek van olyan (jó) színezése, melyben minden szín
legalább kétszer előfordul. Mutassuk meg, hogy ekkor
G
-nek van ilyen színezése
χ
G
színnel.
- 5. feladat Ö M
(a) Tegyük fel, hogy
|
V
G
|
=
n
és
V
G
-nek van olyan
{
V
1
,
…
,
V
k
}
partíciója, melyben minden
1
≤
i
<
j
≤
k
-hoz létezik olyan
x
∈
V
i
és
y
∈
V
j
, melyek nem szomszédosak. Ekkor
(b) Legyen
G
egy
n
pontú egyszerű gráf. Ekkor
- 6. feladat Ö M
Mutassuk meg, hogy egy
G
gráf kromatikus száma egyenlő azzal a legkisebb
m
számmal, melyre
(
G
⊕
K
m
a
G
és a teljes
m
-szög Descartes szorzata).
- 7. feladat Ö M
(a)
χ
G
1
×
G
2
≤
min
(
χ
G
1
,
χ
G
2
)
.
(b)
χ
G
×
G
=
χ
G
.
(c)
χ
G
×
K
n
=
min
χ
G
,
n
.
(d)* Mutassuk meg, hogy ha
G
összefüggő és
χ
G
>
n
, akkor
G
×
K
n
-nek egyértelmű az
n
-színezése (a színek permutációjának
erejéig).
(e) Hány
n
-színezése lehet egy gráfnak?
- 8. feladat Ö M
Legyen
S
a pontok halmaza. Ha
S
⊆
V
G
, akkor
G
bármely színezése
S
egy partícióját indukálja. Ágyazzuk
S
-et valamely
G
gráfba úgy, hogy
S
-nek a
G
k
-színezése (
k
≥
3
) által indukált partíciói
(a) az
S
-nek csak 1 elemű osztályokba való partícionálása
(ennek persze csak az
|
S
|
≤
k
esetben van értelme);
(b) az előző kivételével az összes partíció;
(c) csak az
{
S
}
partíció;
(d) az előző kivételével az összes partíció;
(e)* partíciók egy
{
P
1
,
…
,
P
N
}
halmaza.
- 9. feladat Ö M
Ha egy
G
irányított gráfban nincsen
m
hosszú út, akkor
χ
G
≤
m
.
- 10. feladat Ö M
Milyen esetben színezhetjük egy
G
irányított gráf színeit tetszőleges 1, 2,
… számú színnel úgy, hogy minden él
i
színű pontot
i
+
1
színű ponttal köt össze (
1
≤
i
)?
- 11*. feladat Ö M
Bizonyítsuk be, hogy
G
akkor és csak akkor
k
-színezhető, ha irányítható oly módon, hogy
G
bármely
C
körén bármely körüljárási irányba
C
-nek legalább
|
E
C
|
k
éle mutasson.
- 12. feladat Ö M
(a) Legyen
G
összefüggő gráf és tegyük fel, hogy
G
minden
x
pontjához hozzárendeljük színek egy
C
x
halmazát. Tegyük fel, hogy
|
C
x
|
≥
d
G
x
minden
x
-re és legalább egy
x
0
-ra az egyenlőtlenség szigorúan teljesül. Ekkor
létezik a
G
-nek egy (jó) színezése, mely minden pontban az
előírt színek közül használ egyet.
(b) Tegyük fel ismét, hogy a
G
gráf minden
x
pontjához hozzárendeltünk egy
C
x
szín-halmazt, de most legyen
|
C
x
|
=
d
G
x
minden pontra és
C
a
≠
C
b
valamely
a
,
b
esetén. Továbbá tegyük fel, hogy
G
2-szeresen összefüggő. Mutassuk meg, hogy
G
-nek van (jó) színezése, mely minden
x
pontra annak színezéséhez
C
x
egyik színét használja. (Felhívjuk a figyelmet
arra a fontos speciális esetre, amikor
G
kör; vö. 9.8d megoldásával.)
- 13*. feladat (Brooks tétele) Ö M
(a) Mutassuk meg, hogy ha
G
minden pontjának fokszáma legfeljebb
k
(
≥
3
) és
G
3-szorosan összefüggő, de nem teljes
k
+
1
-gráf, akkor
χ
G
≤
k
(azaz ebben az esetben elhagyható az a feltétel,
hogy
C
x
nem azonos minden pontra).
(b) Mutassuk meg, hogy a 3-szoros összefüggőség helyett
elegendő az összefüggőséget feltenni.
- 14*. feladat Ö M
(a) Legyen
G
végtelen[]
gráf, melynek minden véges részgráfja
k
-színezhető, de ha bármely két nem szomszédos
pontját éllel összekötjük, akkor lesz olyan véges részgráfja, mely nem
k
-színezhető. Bizonyítsuk be, hogy
V
G
partícionálható úgy, hogy két pont akkor és csak
akkor szomszédos, ha különböző osztályba tartoznak.
(b) (Erdős–de Bruijn tétel) Tegyük fel, hogy egy végtelen
G
gráf minden véges részgráfja
k
-színezhető. Bizonyítsuk be, hogy ekkor
G
maga is
k
-színezhető.
(c) Minden
v
∈
V
G
pontra legyen
T
v
az
1
,
…
,
k
pontok diszkrét topologikus terének egy példánya.
Ekkor
V
G
k
színnel való színezéseit tekinthetjük úgy, mint a
∏
v
∈
V
G
T
v
topologikus szorzat-tér pontjait. Bizonyítsuk be,
hogy
G
érvényes színezései zárt részhalmazt alkotnak.
Adjunk ebből új bizonyítást az Erdős–de Bruijn tételre.
- 15. feladat Ö M
Legyen
K
≠
∅
egyszerű gráfok egy halmaza, mely eleget tesz a
következő feltételeknek:
(i) Ha
G
∈
K
és
G
-nek van homomorfizmusa
G
′
-be, akkor
G
′
∈
K
.
(ii) Ha
G
gráf és
a
,
b
,
c
∈
V
G
olyanok, hogy
a
és
c
szomszédosak, de
b
egyikükkel sem szomszédos, és ha
G
+
a
,
b
∈
K
és
G
+
b
,
c
∈
K
, akkor
G
∈
K
.
Bizonyítsuk be, hogy
K
az összes nem
k
-színezhető gráfból áll valamely
k
≥
0
-ra.
- 16*. feladat (Hajós konstrukció) Ö M
Tekintsük az egyszerű gráfokon értelmezett következő operációkat:
(
α
) Új élek és/vagy pontok hozzávétele a gráfhoz,
(
β
) Két nem szomszédos pont azonosítása (és az
esetleg így keletkező él-többszöröződések eltörlése),
(
γ
) Két
G
1
,
G
2
gráfra és
x
i
,
y
i
∈
E
G
i
-ra
x
i
,
y
i
(
i
=
1
,
2
) elhagyása, egy új
y
1
,
y
2
él felvétele, majd
x
1
és
x
2
azonosítása.
Mutassuk meg, hogy ezen operációk nem-
k
-színezhető gráfokból nem-
k
-színezhetőket eredményeznek, és hogy minden nem-
k
-színezhető gráf előáll ezen operációk
ismétlésével a teljes
k
+
1
-szögből kiindulva (a 6. ábra mutatja, hogy hogyan
jutunk el
K
4
-ből az 5-kerékbe).
- 17. feladat Ö M
(a) Mely gráfok kritikusan 3-kromatikusak?
(b) Konstruáljunk kritikusan 4-kromatikus
4
n
pontú gráfokat, melyekben az élek száma legalább
n
2
.
(c) Konstruáljunk kritikusan 6-kromatikus
2
n
pontú gráfokat, melyekben minden pont foka
legalább
n
.
- 18. feladat Ö M
Egy
χ
-kritikus
G
gráf minden
x
pontjához hozzárendelünk egy új
x
′
pontot, és összekötjük
x
minden
G
-beli szomszédjával. Veszünk még egy új
y
pontot, és összekötjük az
x
′
pontokkal (
x
∈
V
G
). Mutassuk meg, hogy az eredményül kapott
G
′
gráf
χ
-kritikus
χ
G
′
=
χ
G
+
1
-gyel.
- 19. feladat Ö M
(a) A 7. ábrán látható gráf feszített részgráfja-e
valamely kritikusan 4-kromatikus gráfnak?
(b) Egy
G
0
gráf akkor és csak akkor részgráfja (vagy
feszített részgráfja) egy kritikusan
k
+
1
-kromatikus
G
gráfnak, ha
χ
G
0
∕
e
≤
k
minden
e
élre.
- 20. feladat Ö M
Ha felosztjuk egy kritikusan
k
+
1
-kromatikus
G
gráf egy pontját, a kapott
G
′
gráf vagy
k
-kromatikus, vagy kritikusan
k
+
1
-kromatikus. Mely
k
értékek esetén eshet meg az utóbbi?
- 21. feladat Ö M
Egy kritikusan
k
+
1
-kromatikus gráf legalább
k
-szorosan élösszefüggő.
- 22. feladat Ö M
Minden
χ
-kritikus gráf 2-szeresen összefüggő. Ezek közül
melyek nem 3-szorosan összefüggőek?
- 23. feladat Ö M
Mutassuk meg, hogy ha
G
egy
χ
-kritikus gráf,
χ
G
=
k
+
1
és
S
egy
m
elemszámú lefogó ponthalmaz, akkor
G
−
S
komponenseinek száma nem nagyobb
m
dolog legfeljebb
k
osztályba való sorolásainak
B
m
,
k
számánl. Mutassuk meg azt is, hogy ez a lehető legjobb.
- 24. feladat Ö M
Legyen
G
kritikusan
k
+
1
-kromatikus gráf. Bizonyítsuk be, hogy minden nem
szomszédos pontpár összeköthető
k
−
1
él-diszjunkt húrmentes páros úttal.
- 25. feladat Ö M
Határozzuk meg a következő gráfok kromatikus számát:
(a)
K
n
élgráfja,
(b) a komplementere,
(c) a
K
→
n
szimmetrikus irányított gráf élgráfja, melyet
K
n
-ből minden él két ellentétesen irányított éllel
való helyettesítésével kapunk. (Felhasználhatjuk
13.21-et.)
- 26. feladat Ö M
(a) Legyen
G
irányított gráf és
L
G
az élgráfja. Bizonyítsuk be, hogy
Továbbá
G
éleit átirányíthatjuk úgy, hogy itt egyenlőség
teljesüljön.
(b)* Ha
G
szimmetrikus irányított gráf, akkor
(az élgráf szempontjából a szimmetrikus irányított gráf
nem azonosítható az irányítatlan gráffal!).
- 27. feladat Ö M
(a) Konstruáljunk háromszögmentes
k
-kromatikus gráfot.
(b)* Konstruáljunk 3-, 4- és 5-hosszú körmentes
k
-kromatikus gráfot.
(c) Konstruáljunk olyan gráfot, melyben nincsen
2
s
+
1
-nél rövidebb páratlan kör és melynek kromatikus
száma nagyobb
k
-nál[].
- 28. feladat Ö M
Legyenek
I
1
,
…
,
I
n
zárt intervallumok egy egyenesen. Definiáljuk a
G
gráfot az
{
x
1
,
…
,
x
n
}
halmazon úgy, hogy
x
ν
és
x
μ
akkor és csak akkor van összekötve, ha
I
ν
∩
I
μ
≠
∅
.
(a) Mutassuk meg, hogy a kapott
G
gráfra
χ
G
=
ω
G
.
(b) Mutassuk meg, hogy ezen gráf
G
¯
komplementerére szintén
χ
G
¯
=
ω
G
¯
.
(c) Mutassuk meg, hogy
G
minden háromnál hosszabb
C
körének van húrja.
- 29. feladat Ö M
(a) Legyen
G
olyan gráf, melynek minden háromnál hosszabb
körének van húrja. Mutassuk meg, hogy
G
minden (tartalmazásra nézve) minimális
S
vágáshalmaza teljes gráfot indukál.
(b) Egy
G
gráf akkor és csak akkor rendelkezik azzal a
tulajdonsággal, hogy minden háromnál hosszabb körének van húrja, ha
reprezentálható a következőképpen: Legyenek
F
1
,
…
,
F
n
a
T
fa részfái; legyen
V
G
=
{
x
1
,
…
,
x
n
}
és akkor és csak akkor kössük össze
x
i
-t
x
j
-vel, ha
F
i
∩
F
j
≠
∅
.
(c) Ha
G
-nek nincsen háromnál hosszabb húrmentes köre,
akkor
χ
G
=
ω
G
, és ugyanez igaz a
G
komplementerére is.
- 30. feladat Ö M
Legyen
G
páros gráf. Ekkor
χ
G
¯
=
ω
G
¯
.
- 31. feladat Ö M
Ha mind
G
1
, mind
G
2
eleget tesz a
χ
G
i
=
ω
G
i
feltételnek, akkor eleget tesz a
G
1
⋅
G
2
erős szorzatuk is.
- 32. feladat Ö M
Legyen
P
parciálisan rendezett halmaz, és definiáljuk a
G
gráfot
P
-n úgy, hogy
x
,
y
∈
P
akkor és csak akkor van összekötve, ha
x
≤
y
vagy
y
≤
x
.
(a) Mutassuk meg, hogy
χ
G
=
ω
G
.
(b) Bizonyítsuk be ugyanezt
G
komplementerére.
- 33. feladat Ö M
Az előző feladatok közül melyek adnak perfekt
gráfot?[]
- 34. feladat Ö M
Egy
G
gráf akkor és csak akkor perfekt, ha minden
G
′
feszített részgráfja tartalmaz olyan független
halmazt, mely
G
′
minden maximális klikkét metszi.
- 35*. feladat Ö M
Mutassuk meg, hogy a
G
perfekt gráf minden
x
pontját egy
G
x
perfekt gráffal helyettesítve egy
G
′
perfekt gráfot kapunk.
- 36. feladat Ö M
Mutassuk meg, hogy egy
G
gráf kromatikus polinomja a színek
λ
számában polinom és határozzuk meg a fokát.
- 37. feladat Ö M
Mutassuk meg, hogy
ahol
c
T
=
c
(
V
G
;
T
)
.
- 38. feladat Ö M
Mutassuk meg, hogy
- 39. feladat Ö M
Határozzuk meg teljes gráfok, fák, körök és
kerekek kromatikus polinomját.
- 40. feladat Ö M
Fejezzük ki
G
kromatikus polinomját, ha adva van
(a) komponenseinek, illetve
(b) tagjainak
kromatikus polinomja.
- 41. feladat Ö M
Határozzuk meg egy intervallumgráf kromatikus
polinomját.
- 42. feladat Ö M
Ha
G
-ben nincsen hurok, akkor
ahol
a
i
≥
0
. Mi az
a
n
−
1
? Próbáljuk meg interpretálni
a
1
-et. (Itt
n
a pontok számát jelöli.)
- 43. feladat Ö M
Ha
G
összefüggő, akkor
a
i
>
0
(
i
=
1
,
…
,
n
−
1
) és
a
n
−
1
<
a
n
−
2
<
…
a
⌊
n
∕
2
⌋
+
1
.
- 44. feladat Ö M
Legyen
x
0
a
P
G
λ
legnagyobb valós gyöke. Mutassuk meg, hogy
x
0
≤
n
−
1
.
- 45. feladat Ö M
Mutassuk meg, hogy
P
G
λ
-nak nincsen gyöke a
0
,
1
intervallumban.
- 46. feladat Ö M
(a) Mi a jelentése a kromatikus polinom 0 és 1
gyökei multiplicitásának?
(b) Bizonyítsuk be, hogy
|
P
G
−
1
|
a
G
irányított körmentes irányításainak száma.
- 47*. feladat Ö M
(a) Legyen
G
síkgráf az
F
négyszög-lappal. Legyen
e
1
és
e
2
az
F
két átlója és
G
i
=
G
+
e
i
(
i
=
1
,
2
). Keressünk összefüggést
P
G
1
λ
,
P
G
2
λ
,
P
G
1
∕
e
1
λ
és
P
G
2
∕
e
2
λ
között.
(b) Van-e olyan
alakú lineáris összefüggés valamely rögzített egész
a
,
b
,
c
értékekkel (nem mind nullák), mely minden
G
és
λ
esetén fennáll? Mutassuk meg, hogy legfeljebb öt
eset kivételével nincs ilyen összefüggés, még rögzített
λ
érték mellett sem.
(c) Legyen
τ
=
5
+
1
2
. Ekkor
- 48. feladat Ö M
Mutassuk meg, hogy
τ
+
1
nem gyöke egyetlen kromatikus polinomnak
sem.
- 49*. feladat (Aranymetszés tétele) Ö M
(a) Ha
G
egy
n
pontú síkbarajzolható háromszögelt gráf, akkor
(b)[]
Bármely síkbarajzolható
G
gráfra
- 50. feladat Ö M
A hurokmentes síkbarajzolható
G
gráf kromatikus száma legfeljebb 5.
- 51. feladat Ö M
Adva van egy 3-reguláris, 2-szeresen összefüggő
síkgráf, lapjait akkor és csak akkor színezhetjük 4 színnel (oly
módon, hogy szomszédos lapok színe különböző), ha kromatikus indexe
3.
- 52. feladat Ö M
Legyen
G
3-reguláris, 2-szeresen összefüggő síkgráf. Ekkor
G
lapjai akkor és csak akkor 4-színezhetők, ha a
+
1
,
−
1
számok valamelyikét hozzárendelhetjük minden
ponthoz úgy, hogy bármely lapra a vele érintkező pontokhoz rendelt
számok összege osztható hárommal.
- 53. feladat Ö M
Tegyük fel, hogy egy síkgráfban van Hamilton kör.
Mutassuk meg, hogy lapjai 4-színezhetők.
- 54*. feladat Ö M
(a) Az összefüggő
G
síkgráf minden fokszáma legfeljebb 5, és legalább
egy pontjának fokszáma legfeljebb 4. Bizonyítsuk be, hogy
G
4-színezhető.
(b) Mutassuk meg, hogy minden 5-reguláris síkgráf is
4-színezhető.
- 55. feladat Ö M
Minden egyszerű síkgráf pontjait kiszínezhetjük
két színnel úgy, hogy minden lapja mindkét színnel
érintkezik.
- 56. feladat Ö M
Egy háromszögelt síkgráf akkor és csak akkor
3-színezhető, ha minden pontjának a foka páros.
- 57. feladat Ö M
Rajzoljunk a síkba egyeneseket úgy, hogy nincsen
köztük 3, melyek egy pontban metszik egymást. Tekintsük a
metszéspontokat egy gráf pontjainak, és a szomszédos metszéspontok
közötti szakaszokat a gráf éleinek. Bizonyítsuk be, hogy a kapott
síkbarajzolható gráf 3-színezhető.