תוצאות החיפוש

[[קובץ:Complete-edge-coloring.svg|ממוזער|צביעה של [[גרף שלם|הגרף השלם]] על שמונה קודקודים]] [[Image:PetersenBarveniHran.svg|thumb|left|צביעה בארבעה צבעים של גרף פיטרסן]] ...

...ם מספר תנאים (קשיר היטב ואורכי המעגלים שלו צריכים להיות זרים במשותף) קיימת צביעה של הקשתות עבורה יש מילה מסנכרנת.{{הערה|1= ...צביעה שעבורה יש לאוטומט מילה מסנכרנת, נקראת '''צביעה מסנכרנת'''. כדי שתהיה צביעה כזו, הגרף מוכרח לקיים שתי דרישות: הוא צריך להיות [[גרף קשיר|קשיר כגרף מכוון ...

* כל [[גרף n-צביע|צביעה]] חמדנית של כל תת-גרף מושרה היא אופטימלית ...

=== צביעה של גרף מיתרי === קל לראות שאלגוריתם זה מוביל ל[[גרף n-צביע|צביעה]] במספר מינימלי של צבעים. נניח בשלילה שלא כך הוא, ונתבונן בגרף מיתרי <math> ...

[[קובץ:Triangulation 3-coloring.svg|ממוזער|צביעה בשלושה צבעים של מצולע שעבר שילוש. מספר הקודקודים הכחולים הוא הקטן ביותר (3 ...מצולע, כך ששני קודקודים המחוברים בקו לא יהיו בעלי אותו צבע. ניתן להוכיח כי צביעה שכזו תמיד אפשרית וגם לספק [[אלגוריתם]] למציאתה (ההוכחה מבוססת על כך ש[[גרף ...

'''משפט'''. לכל צביעה של הגרף האינסופי ה[[גרף שלם|שלם]] <math>\ G</math> בשני צבעים, קיים תת-גרף ...th>, יש תת-גרף מונוכרומטי שעוצמתו גדולה מ-<math>\ \kappa</math>. למשל, בכל צביעה של הגרף השלם שעוצמת קבוצת הקודקודים שלו גדולה מ-<math>\ 2^{\aleph_0}</math> ...

...לים מ-1), יש חלק הכולל מספרים שסכום ההופכיים שלהם הוא 1. במילים אחרות, לכל צביעה של המספרים האלו במספר סופי של צבעים, יש "הצגה מונוכרומטית" של 1 כ[[שבר מצרי ...ו כך שסכום ההופכיים של כל המספרים החלקים הוא לפחות ''6r'', משום שאז יש בכל צביעה ב-r צבעים חלק אחד שסכום ההופכיים עבורו הוא לפחות 6. ...

[[צביעה של גרף]] היא התאמה של צבע לכל צומת כך שאין שני צמתים בעלי צבע זהה המחוברים קל להדגים צביעה שאכן משתמשת ב-<math>n-2k+2</math> צבעים, והדבר נעשה כבר על ידי קנזר. הקושי ...

=== מספר ה3-צביעה === {{ערך מורחב|מספר השלוש-צביעה}} ...

...נגולציה]] של [[משולש]] למשולשים יותר קטנים, נניח כי קיימת [[גרף n-צביע|תלת צביעה]] של קיימת הכללה של הלמה למימד <math>d \in \mathbb{N}</math> טבעי כלשהו עבור צביעה של קודקודי טריאנגולציה של [[סימפלקס]] <math>d</math> ממדי. במקרה כזה, צביעת ...

...ו פחות. בלשון אחרת, המשפט מבטיח שלכל גרף מישורי יש 4-[[צביעה (תורת הגרפים)|צביעה]]. ...

...ש זרימת-k לא מתאפסת אם ורק אם לגרף הדואלי (המתאים לפנים של הגרף המשוכן) יש צביעה בקודקודים עם k צבעים. בגרף ללא גשרים שלכל קודקודיו דרגה 3 ניתן לצבוע את ק ...

גרף מדרגה 3 ניתן ל-3-צביעה [[אם ורק אם]] יש בו [[זרימה לא מתאפסת]] עם ערכים ב[[חבורת הארבעה של קליין]] ...

...שת]] בגרף בצבע אדום או שחור. מהו הערך המינימלי של <math>\ n</math> כך שלכל צביעה אפשרית של הגרף בהכרח יהיה קיים [[תת-גרף]] שלם עם ארבעה קודקודים, הנמצאים בא ...

הבעיה שואלת האם יש צביעה בוליאנית (בשני צבעים, למשל אדום וכחול) של ה[[מספר טבעי|מספרים הטבעיים]], כך ...

...קודים]] בארבעה צבעים. אנשי תורת הגרפים מכירים הוכחות קלות יחסית לכך שקיימת צביעה ב'''חמישה''' צבעים, אבל ההוכחה לכך שאפשר להסתפק בארבעה נמצאה רק ב-[[1976]], ...ירת צבע לכל קודקוד, באופן כזה שלשני קודקודים המחוברים בקשת יש צבעים שונים. צביעה כזו של הגרף נקראת [[צביעת קודקודים]]. ...

...th> צביעות בצבע אחד, והשאר, <math>a^p-a</math>, בשני צבעים שונים לפחות. כל צביעה כזו מופיעה בדיוק <math>p</math> פעמים, ולכן מספר המצולעים השונים הוא <math> ...

ייצוג תחום הצבעים האפורים משתנה משיטת צביעה אחת לאחרת: ...

...בוססי הטיטניום נכללים [[פיגמנטי צביעה#לבן טיטניום|לבן טיטניום]] ו[[פיגמנטי צביעה#צהוב ניקל טיטניום|צהוב ניקל טיטניום]]. ...

...ודות אדומות, והסביבה של כל נקודה ירוקה תכלול רק נקודות ירוקות. בטבעת מביוס צביעה כזו היא בלתי אפשרית.]] ...