Графтарды түстің тізімімен бояу – математикадағы график теориясының бір саласы. Тізімдік бояу, қанағаттандыру шарттары, k-қосылатын графиктар туралы біліңіз.
Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Мазмұны
Кіріспе
Графтар теориясында, математиканың бір саласы, тізімдік бояу – әрбір төбеге рұқсат етілген түстер тізімімен шектеу қойылатын график бояу түрі. Оны алғаш рет 1970 жылдары Визинг, сондай-ақ Эрдос, Рубин және Тейлор дербес зерттемелерінде қарастырған.
In graph theory, a branch of mathematics, list coloring is a type of graph coloring where each vertex can be restricted to a list of allowed colors. It was first studied in the 1970s in independent papers by Vizing
and by Erdős, Rubin, and Taylor.
Анықтама
График G және әрбір төбе v үшін L(v) түстер жиыны (тізім деп аталады) берілгенде, тізімдік бояу – бұл әрбір төбе v-ні L(v) тізімінен түске бейімдейтін таңдау функциясы. Графты бояу сияқты, тізімдік бояу да әдетте дұрыс деп есептеледі, яғни екі жапсарлас төбелер бірдей түс алмайды. Егер графтың әрбір төбесіне k түстің тізімін қалай тағайындағанға қарамастан, дұрыс тізімдік бояу болса, онда граф k-таңдамалы (немесе k-тізімдік боялатын) болады. График G-нің таңдамалығы (немесе тізімдік боялатындығы немесе тізімдік хроматикалық саны) ch(G) – G-нің k-таңдамалы болуы үшін қажетті ең кішкентай k саны. Көбірек айтқанда, егер әрбір төбе v үшін f функциясы оң бүтін сан f(v)-ні тағайындаса, граф G f-таңдамалы (немесе f-тізімдік боялатын) болады, егер әрбір төбе v үшін f(v) түстің тізімін қалай тағайындағанға қарамастан, тізімдік бояуы болса. Атап айтқанда, егер барлық төбелер v үшін f(v) = k болса, f-таңдамалығы k-таңдамалығымен сәйкес келеді.
Given a graph G and given a set L(v) of colors for each vertex v (called a list), a list coloring is a choice function that maps every vertex v to a color in the list L(v). As with graph coloring, a list coloring is generally assumed to be proper, meaning no two adjacent vertices receive the same color. A graph is k choosable (or k list colorable) if it has a proper list coloring no matter how one assigns a list of k colors to each vertex. The choosability (or list colorability or list chromatic number) ch(G) of a graph G is the least number k such that G is k choosable. More generally, for a function f assigning a positive integer f(v) to each vertex v, a graph G is f choosable (or f list colorable) if it has a list coloring no matter how one assigns a list of f(v) colors to each vertex v. In particular, if for all vertices v, f choosability corresponds to k choosability.
Мысалдар
G = K2,4 толық екі бөлікті графигін қарастырайық, оның алты төбесі A, B, W, X, Y, Z, мұнда A және B әрқайсысы W, X, Y және Z-ның бәрімен байланысты, ал басқа төбелердің арасында байланыс жоқ. Екі бөлікті график ретінде G-дің әдеттегі түстік саны 2-ге тең: A және B-ні бір түспен, ал W, X, Y, Z-ді басқа түспен бояуға болады, сонда екі іргелес төбелердің түсі бірдей болмайды. Екінші жағынан, G-дің тізімдік түстік саны 2-ден үлкен, бұл келесі құрылымнан көрінеді: A және B төбелеріне {қызыл, көк} және {жасыл, қара} тізімдерін беріңіз. Қалған төрт төбеге {қызыл, жасыл}, {қызыл, қара}, {көк, жасыл} және {көк, қара} тізімдерін тағайындаңыз. A тізімінен түс таңдағанда да, B тізімінен түс таңдағанда да, олардың екеуі де көрші төбелерін бояу үшін қолданылған түстердің арасында болады. Осылайша, G 2-ге таңдауға жарамды емес. Екінші жағынан, G-нің 3-ке таңдауға болатындығын көру оңай: A және B төбелеріне кездейсоқ түстерді таңдау қалған төбелердің әрқайсысы үшін кем дегенде бір қолжетімді түс қалдырады, ал осы түстерді кездейсоқ таңдауға болады. Жалпы алғанда, q – оң бүтін сан болсын, ал G – Kq,qq толық екі бөлікті графигі болсын. Қолжетімді түстерді q-лық радикстегі q2 әртүрлі екі таңбалы санмен бейнелейік. Екі бөліктің бір жағындағы q төбелеріне {i0, i1, i2, …} түстер жиынтығын беріңіз, мұнда бірінші таңбалардың барлығы әрбір q мүмкін таңдау үшін i-ге тең. Екі бөліктің екінші жағындағы qq төбелеріне {0a, 1b, 2c, …} түстер жиынтығын беріңіз, мұнда бірінші таңбалардың барлығы әрбір qq мүмкін таңдау үшін q-лық тупл (a, b, c, …) үшін әртүрлі. Суретте осы құрылымның үлкенірек мысалы көрсетілген, мұнда q = 3. Онда G-де L үшін түстік жоқ: екі бөліктің кіші жағындағы төбелер үшін қандай түстер жиынтығы таңдалғанына қарамастан, бұл таңдау екі бөліктің екінші жағындағы төбелердің бірі үшін барлық түстермен қайшылыққа түседі. Мысалы, егер {00, 01} түстер жиынтығы 01 түсімен, ал {10, 11} түстер жиынтығы 10 түсімен боялса, онда {01, 10} түстер жиынтығын бояу мүмкін емес. Сондықтан G-дің тізімдік түстік саны кем дегенде q + 1-ге тең. Сол сияқты, егер , онда толық екі бөлікті граф Kn,n k-ға таңдауға жарамсыз. Себебі, барлығы 2k − 1 түс бар деп есептейік, және екі бөліктің бір жағындағы әр төбе басқа төбелерден өзгеше k-лық тупл түстеріне ие. Онда екі бөліктің әр жағында кем дегенде k түс қолданылуы керек, өйткені k - 1 түстің әр жиынтығы бір төбенің тізімінен өзгеше болады. Кем дегенде k түс бір жағында және кем дегенде k түс екінші жағында қолданылғандықтан, екі жағында да қолданылатын бір түс болуы керек, бірақ бұл екі іргелес төбелердің бірдей түске ие екенін білдіреді. Атап айтқанда, K3,3 пайдалы графигінің тізімдік түстік саны кем дегенде үш, ал K10,10 графигінің тізімдік түстік саны кем дегенде төрт.
Consider the complete bipartite graph G = K2,4, having six vertices A, B, W, X, Y, Z such that A and B are each connected to all of W, X, Y, and Z, and no other vertices are connected. As a bipartite graph, G has usual chromatic number 2: one may color A and B in one color and W, X, Y, Z in another and no two adjacent vertices will have the same color. On the other hand, G has list chromatic number larger than 2, as the following construction shows: assign to A and B the lists {red, blue} and {green, black}. Assign to the other four vertices the lists {red, green}, {red, black}, {blue, green}, and {blue, black}. No matter which choice one makes of a color from the list of A and a color from the list of B, there will be some other vertex such that both of its choices are already used to color its neighbors. Thus, G is not 2 choosable. On the other hand, it is easy to see that G is 3 choosable: picking arbitrary colors for the vertices A and B leaves at least one available color for each of the remaining vertices, and these colors may be chosen arbitrarily. More generally, let q be a positive integer, and let G be the complete bipartite graph Kq,qq. Let the available colors be represented by the q2 different two digit numbers in radix q. On one side of the bipartition, let the q vertices be given sets of colors {i0, i1, i2, } in which the first digits are equal to each other, for each of the q possible choices of the first digit i. On the other side of the bipartition, let the qq vertices be given sets of colors {0a, 1b, 2c, } in which the first digits are all distinct, for each of the qq possible choices of the q tuple (a, b, c, ). The illustration shows a larger example of the same construction, with q = 3. Then, G does not have a list coloring for L: no matter what set of colors is chosen for the vertices on the small side of the bipartition, this choice will conflict with all of the colors for one of the vertices on the other side of the bipartition. For instance if the vertex with color set {00,01} is colored 01, and the vertex with color set {10,11} is colored 10, then the vertex with color set {01,10} cannot be colored. Therefore, the list chromatic number of G is at least q + 1. Similarly, if , then the complete bipartite graph Kn, n is not k choosable. For, suppose that 2k − 1 colors are available in total, and that, on a single side of the bipartition, each vertex has available to it a different k tuple of these colors than each other vertex. Then, each side of the bipartition must use at least k colors, because every set of k − 1 colors will be disjoint from the list of one vertex. Since at least k colors are used on one side and at least k are used on the other, there must be one color which is used on both sides, but this implies that two adjacent vertices have the same color. In particular, the utility graph K3,3 has list chromatic number at least three, and the graph K10,10 has list chromatic number at least four.
Қасиеттері
G графигі үшін χ(G) – хроматикалық санды, ал Δ(G) – G графигінің ең жоғары дәрежесін белгілейміз. Тізімдік түстеу саны ch(G) келесі қасиеттерге ие: ch(G) ≥ χ(G). k тізімдік түстеуге болатын граф, әсіресе, әр төбесіне бірдей k түстің тізімі берілгенде, тізімдік түстеу болуы керек, бұл кез келген k түстеуге сәйкес келеді. ch(G) жалпы жағдайда хроматикалық сан арқылы шектеле алмайды, яғни, әр граф G үшін ch(G) ≤ f(χ(G)) шартын орындауға болатын f функциясы жоқ. Атап айтқанда, толық екібөлікті граф мысалдары көрсеткендей, χ(G) = 2 болатын, бірақ ch(G) кез келгеннен үлкен графтар бар. ch(G) ≤ Δ(G) + 1. Егер G жазық граф болса, онда ch(G) ≤ 5. Егер G екібөлікті жазық граф болса, онда ch(G) ≤ 3.
For a graph G, let χ(G) denote the chromatic number and Δ(G) the maximum degree of G. The list coloring number ch(G) satisfies the following properties. ch(G) ≥ χ(G). A k list colorable graph must in particular have a list coloring when every vertex is assigned the same list of k colors, which corresponds to a usual k coloring. ch(G) cannot be bounded in terms of chromatic number in general, that is, there is no function f such that ch(G) ≤ f(χ(G)) holds for every graph G. In particular, as the complete bipartite graph examples show, there exist graphs with χ(G) = 2 but with ch(G) arbitrarily large. ch(G) ≤ Δ(G) + 1.
ch(G) ≤ 5 if G is a planar graph. ch(G) ≤ 3 if G is a bipartite planar graph.