Späť

Podgrafy 4-kritických planárnych grafov

Subgraphs of 4-critical planar graph

RNDr. Peter Hudák
Univerzita Pavla Jozefa Šafárika v Košiciach, Prírodovedecká fakulta
Ústav matematických vied
Jesenná 5, 040 01 Košice

Abstrakt:
Hovoríme, že graf je k-kritický ak jeho chromatické číslo je k a každý jeho vlastný podgraf je (k-1)-farbiteľný. V roku 1974 Greenwell a Lovász [1] charakterizovali triedu vlastných podgrafov k-kritických grafov. (k-1)-farbiteľný graf je vlastným podgrafom nejakého k-kritického grafu práve vtedy, keď kontrahovaním ľubovoľnej jeho hrany e, graf G/e je (k-1)-farbiteľný. Je ľahké overiť, že táto veta nebude platiť ak budeme uvažovať iba triedu 4-kritických planárnych grafov. Budeme prezentovať výsledky o vlastnostiach niektorých podgrafov 4-kritických planárnych grafov. Taktiež uvedieme príklad zakázaných podgrafov 4-kritických planárnych grafov, ktoré spĺňajú Greenwell, Lovász podmienku. Literatúra [1] D. Greenwell, L. Lov_x0013_ász, Applications of product colouring, Aeta Math. Acad. Sci. Hungar. 25 (1974), 335-340.

Kľúčové slová:
planárny graf, kritický graf, chromatické číslo, podgraf, farbenie

Abstract:
A graph is k-critical if its chromatic number is k and each its proper subgraph is (k-1)-colorable. In 1974 Greenwell and Lov_x0013_ász [1] characterized the class of all proper subgraphs of k-critical graphs. A (k-1)-colorable graph is proper subgraph of some k-critical graph if and only if by contracting arbitrary edge e graph G/e is(k-1)-colorable. It is easy to verify that this theorem is not valid if we consider class of 4-critical planar graphs. We will present results about properties of some subgraphs of 4-critical planar graphs. We will also show some examples of forbidden subgraphs of 4-critical planar graphs that ful_x000C_fill Greenwell, Lov_x0013_ász condition. References [1] D. Greenwell, L. Lov_x0013_ász, Applications of product colouring, Aeta Math. Acad. Sci. Hungar. 25 (1974), 335-340.

Keywords:
planar graph, critical graph, chromatic number, subgraph, coloring

Späť